[squeakdev] The Trunk: Collectionsnice.829.mcz
commits at source.squeak.org
commits at source.squeak.org
Fri May 3 21:06:20 UTC 2019
Nicolas Cellier uploaded a new version of Collections to project The Trunk:
http://source.squeak.org/trunk/Collectionsnice.829.mcz
==================== Summary ====================
Name: Collectionsnice.829
Author: nice
Time: 3 May 2019, 11:06:11.65639 pm
UUID: 695419ed754d41ff8b51b8715934b1f5
Ancestors: Collectionsfn.828
Remove unused digitShiftSum: (since Kernelnice.1224)
=============== Diff against Collectionsfn.828 ===============
Item was removed:
  Method: Interval>>digitShiftSum: (in category 'enumerating') 
 digitShiftSum: aBlock
 "Reconstruct an Integer that has been split in chunks by using shift and add.
 Each of my element represent a digitShift, an my step size repreent the digit length of chunks.
 The block is evaluated with each digitShift to produce the chunks.

 Algorithm insights:
 Let d0,d1,d2,... be the chunks, and s be the bit shift (8*step because digitLength is 8bits)
 The naive loop does shift each chunk and accumulate into a sum:
 ((d0 + (d1<<s)) + (d2<<s)) + (d3<<s) + ...
 The length of accumulator increase at each iteration (1+2+3...) resulting in a cost (size+1)*size/2, or O(size^2)
 Note that Horner scheme would be of about same cost
 (((... + d3) << s + d2) << s + d1) << s + d0
 (a bit like so called Shlemiel the painter)
 If we instead divide and conquer, we add smaller parts (1+1+2+...) resulting into a cost of O(size*log2(size))
 (d0 + (d1<<s)) + ((d2 + (d3<<s)) << s) + ...
 However, the divide and conquer split comes with an additionnal cost, so do it only if worth it."

  sz half offset 
 "Naive loop in O(size^2)/2 is best for small size"
 (sz := self size) <= 8 ifTrue: [^self inject: 0 into: [:sum :shift  ((aBlock value: shift) bitShift: 8 * shift) + sum]].
 half := sz // 2.
 offset := half * step + start.
 ^((start to: half  1 * step + start by: step) digitShiftSum: aBlock)
 + (((0 to: self last  offset by: step) digitShiftSum: [:k  aBlock value: offset + k]) bitShift: 8 * offset)!
More information about the Squeakdev
mailing list
