<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Mon, Jan 19, 2015 at 11:32 AM, Levente Uzonyi <span dir="ltr"><<a href="mailto:leves@elte.hu" target="_blank">leves@elte.hu</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span class="">I never said it was easy.<br>
Another way to do it is to compact eagerly on removal (as it's done in<br>
Pharo). This gives better mass removal performance, and some of the code<br>
becomes significantly simpler. This results in further performance boost.<br>
<br></span>
Removal still takes O(n) time, which means mass removal is in O(n^2), but with a significantly smaller constant (~1/10), which improves the<span class="im HOEnZb"><br>
usability of the collection quite a bit:<br>
<br></span><span class="im HOEnZb">
| n random array |<br>
n := 10000.<br>
random := Random seed: 36rSQUEAK.<br>
array := Array new: n streamContents: [ :stream |<br>
n timesRepeat: [ stream nextPut: (random nextInt: 1073741823) -> 1 ] ].<br>
{ OrderedDictionary. LinkedDictionary } collect: [ :class |<br>
Smalltalk garbageCollect.<br>
[<br>
| instance |<br>
instance := class new.<br>
instance addAll: array.<br>
array do: [ :each | instance removeKey: each key ] ] timeToRun ].<br></span><span class="im HOEnZb">
"==> #(78 10)"<br>
<br>
(If n is 100k, then the result is still pretty bad: #(7055 136).)<br>
<br>
You can find these changes in the Inbox.<br></span></blockquote><div><br></div><div>In Spur, self become: self copyEmpty should be cheap. This takes about 18 usecs on my 2.2GHz i7. So at some point the become will be cheaper for removeAll.</div><div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span class="im HOEnZb">Levente<br>
<br></span><span class="im HOEnZb">
On Mon, 19 Jan 2015, Marcel Taeumel wrote:<br>
<br>
</span><div class="HOEnZb"><div class="h5"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Woah, managing such a lookup index between "array" and "order" is quite<br>
complicated with the current implementation of Dictionary. :D<br>
<br>
Best,<br>
Marcel<br>
<br>
<br>
<br>
--<br>
View this message in context: <a href="http://forum.world.st/The-Trunk-Collections-mt-599-mcz-tp4800299p4800317.html" target="_blank">http://forum.world.st/The-<u></u>Trunk-Collections-mt-599-mcz-<u></u>tp4800299p4800317.html</a><br>
Sent from the Squeak - Dev mailing list archive at Nabble.com.<br>
<br>
<br>
</blockquote>
<br>
</div></div></blockquote></div><br><br clear="all"><div><br></div>-- <br><div class="gmail_signature">best,<div>Eliot</div></div>
</div></div>