Smalltalk › Pharo › Pharo Smalltalk Users

Is there a way to stop arrays sorting automatically?

_‹ Previous Topic Next Topic _›

Classic

List

Threaded

13 messages Options

Andy Burnett

Is there a way to stop arrays sorting automatically?

I suspect I am missing something very obvious, in which case could some kind soul put me straight?

I have the following code

col := OrderedCollection new.

(1 to: 9) permutationsDo: [ :each | col add: (each )].

I thought this would give me a collection containing all the permutations. However, what actually happens is that each of the arrays has been 'magically' sorted back into numerical order. If I change the code to read

col := OrderedCollection new.

(1 to: 9) permutationsDo: [ :each | col add: (each asOrderedCollection )].

Then the permutations are retained. Is this how it is supposed to work? Or, am I doing something wrong?

Cheers

Andy

Ben Coman

Re: Is there a way to stop arrays sorting automatically?

On 31 December 2017 at 04:00, Andy Burnett <[hidden email]> wrote:

I suspect I am missing something very obvious, in which case could some kind soul put me straight?

I have the following code

col := OrderedCollection new.
(1 to: 9) permutationsDo: [ :each | col add: (each )].

I thought this would give me a collection containing all the permutations. However, what actually happens is that each of the arrays has been 'magically' sorted back into numerical order. If I change the code to read

col := OrderedCollection new.
(1 to: 9) permutationsDo: [ :each | col add: (each asOrderedCollection )].

Then the permutations are retained. Is this how it is supposed to work? Or, am I doing something wrong?

Cheers
Andy

Its not so much that your first example sorted the permutations, but that the collection contained only one permutation.

I've swapped the order of your examples and downsized them to the simplest case to observe.

Something seems broken. It works as expected if the "copy" is uncommented.

Transcript clear.

oc1 := OrderedCollection new.

oc2 := OrderedCollection new.

Transcript crShow:'a---'.

(1 to: 3) permutationsDo: [ :each | Transcript crShow: each. oc1 add: each asOrderedCollection].

Transcript crShow:'b---'.

(1 to: 3) permutationsDo: [ :each | Transcript crShow: each. oc2 add: each "copy"].

Transcript crShow:'c---'.

Transcript crShow: { oc1 asSet size. oc2 asSet size}.

Transcript crShow:'d---'.

oc2 do: [ :x | Transcript crShow: x ].

==>

a---

#(1 2 3)

#(1 3 2)

#(2 1 3)

#(2 3 1)

#(3 2 1)

#(3 1 2)

b---

#(1 2 3)

#(1 3 2)

#(2 1 3)

#(2 3 1)

#(3 2 1)

#(3 1 2)

c---

#(6 1)

d---

#(1 2 3)

cheers -ben

Andy Burnett

Re: Is there a way to stop arrays sorting automatically?

In reply to this post by Andy Burnett

Ben wrote >>>

Its not so much that your first example sorted the permutations, but that
the collection contained only one permutation.
I've swapped the order of your examples and downsized them to the simplest
case to observe.
Something seems broken. It works as expected if the "copy" is uncommented.

Transcript clear.
oc1 := OrderedCollection new.
oc2 := OrderedCollection new.
Transcript crShow:'a---'.
(1 to: 3) permutationsDo: [ :each | Transcript crShow: each. oc1 add:
each asOrderedCollection].
Transcript crShow:'b---'.
(1 to: 3) permutationsDo: [ :each | Transcript crShow: each. oc2 add:
each "copy"].
Transcript crShow:'c---'.
Transcript crShow: { oc1 asSet size. oc2 asSet size}.
Transcript crShow:'d---'.
oc2 do: [ :x | Transcript crShow: x ].

==>
a---
#(1 2 3)
#(1 3 2)
#(2 1 3)
#(2 3 1)
#(3 2 1)
#(3 1 2)
b---
#(1 2 3)
#(1 3 2)
#(2 1 3)
#(2 3 1)
#(3 2 1)
#(3 1 2)
c---
#(6 1)
d---
#(1 2 3)
#(1 2 3)
#(1 2 3)
#(1 2 3)
#(1 2 3)
#(1 2 3)

cheers -ben

<<<

Thanks Ben,

That is really interesting. I had completely misunderstood the problem. Checking the items in oc2 shows that they are literally the same object. So, it would seem that I have to run copy, or some other method to get a unique object.

I can see that this would make sense from an efficiency perspective. Reusing the same object would presumably save memory space. However, it would probably be good to update the comment to let people know that this will happen.

What is the process for submitting suggested improvements to class comments?

Cheers

Andy

Denis Kudriashov

Re: Is there a way to stop arrays sorting automatically?

Hi.

2017-12-31 14:47 GMT+01:00 Andy Burnett <[hidden email]>:

Thanks Ben,
That is really interesting. I had completely misunderstood the problem. Checking the items in oc2 shows that they are literally the same object. So, it would seem that I have to run copy, or some other method to get a unique object.

I can see that this would make sense from an efficiency perspective. Reusing the same object would presumably save memory space. However, it would probably be good to update the comment to let people know that this will happen.

What is the process for submitting suggested improvements to class comments?

It's same as any other code. Just follow instructions https://github.com/pharo-project/pharo/wiki/Contribute-a-fix-to-Pharo. It is now simplified a lot.

Cheers
Andy

Andy Burnett

Re: Is there a way to stop arrays sorting automatically?

In reply to this post by Andy Burnett

Denis wrote

>>>

It's same as any other code. Just follow instructions
https://github.com/pharo-project/pharo/wiki/Contribute-a-fix-to-Pharo. It
is now simplified a lot.

<<<

Wow! That has improved a lot. I have bookmarked the site, and I now have a reason to learn iceberg.

Out of curiosity, and perhaps this has been answered elsewhere, why are we using fogbugz for issue tracking, rather than github's issue tracker? I know nothing much about either of them. I am just curious if fogbugz is much better?

Cheers

Andy

CyrilFerlicot

Re: Is there a way to stop arrays sorting automatically?

On dim. 31 déc. 2017 at 16:04, Andy Burnett <[hidden email]> wrote:

Denis wrote
>>>

It's same as any other code. Just follow instructions
https://github.com/pharo-project/pharo/wiki/Contribute-a-fix-to-Pharo. It
is now simplified a lot.

<<<

Wow! That has improved a lot. I have bookmarked the site, and I now have a reason to learn iceberg.

Out of curiosity, and perhaps this has been answered elsewhere, why are we using fogbugz for issue tracking, rather than github's issue tracker? I know nothing much about either of them. I am just curious if fogbugz is much better?

Hi,

I think that one of the reason is that all the Pharo process is based on Fogbugz and migrating would takes month and add a lot of instability for few gain.

Cheers
Andy

Cyril Ferlicot
https://ferlicot.fr

http://www.synectique.eu
2 rue Jacques Prévert 01,
59650 Villeneuve d'ascq France

Stephane Ducasse-3

Re: Is there a way to stop arrays sorting automatically?

In reply to this post by Andy Burnett

On Sun, Dec 31, 2017 at 4:03 PM, Andy Burnett
<[hidden email]> wrote:

> Denis wrote
>>>>
>
> It's same as any other code. Just follow instructions
> https://github.com/pharo-project/pharo/wiki/Contribute-a-fix-to-Pharo. It
> is now simplified a lot.
>
> <<<
>
> Wow! That has improved a lot. I have bookmarked the site, and I now have a
> reason to learn iceberg.
>
> Out of curiosity, and perhaps this has been answered elsewhere, why are we
> using fogbugz for issue tracking, rather than github's issue tracker? I know
> nothing much about either of them. I am just curious if fogbugz is much
> better?

- Free for us (normally it cost 25$ per seat)
- Maintained
- Working
- When we migrated out of this code.google.com the git tracker was
clearly not sexy.
- The new version of fogbugz is working really nicely.

I prefer that we do not lose again a lot of engineering time to
migrate and update our process.
We have too many fronts open right now.
We should really pay attention because starting something is super
easy finishing it super difficult.

Stef

Stephane Ducasse-3

Re: Is there a way to stop arrays sorting automatically?

In reply to this post by Andy Burnett

Would be good to have tests showing the problem.
Did you check if such method is not already covered (even by a bad test)?

Stef

On Sun, Dec 31, 2017 at 2:47 PM, Andy Burnett
<[hidden email]> wrote:

> Ben wrote >>>
>
>
> Its not so much that your first example sorted the permutations, but that
> the collection contained only one permutation.
> I've swapped the order of your examples and downsized them to the simplest
> case to observe.
> Something seems broken. It works as expected if the "copy" is uncommented.
>
> Transcript clear.
> oc1 := OrderedCollection new.
> oc2 := OrderedCollection new.
> Transcript crShow:'a---'.
> (1 to: 3) permutationsDo: [ :each | Transcript crShow: each. oc1 add:
> each asOrderedCollection].
> Transcript crShow:'b---'.
> (1 to: 3) permutationsDo: [ :each | Transcript crShow: each. oc2 add:
> each "copy"].
> Transcript crShow:'c---'.
> Transcript crShow: { oc1 asSet size. oc2 asSet size}.
> Transcript crShow:'d---'.
> oc2 do: [ :x | Transcript crShow: x ].
>
> ==>
> a---
> #(1 2 3)
> #(1 3 2)
> #(2 1 3)
> #(2 3 1)
> #(3 2 1)
> #(3 1 2)
> b---
> #(1 2 3)
> #(1 3 2)
> #(2 1 3)
> #(2 3 1)
> #(3 2 1)
> #(3 1 2)
> c---
> #(6 1)
> d---
> #(1 2 3)
> #(1 2 3)
> #(1 2 3)
> #(1 2 3)
> #(1 2 3)
> #(1 2 3)
>
> cheers -ben
>
> <<<
>
> Thanks Ben,
> That is really interesting. I had completely misunderstood the problem.
> Checking the items in oc2 shows that they are literally the same object. So,
> it would seem that I have to run copy, or some other method to get a unique
> object.
>
> I can see that this would make sense from an efficiency perspective. Reusing
> the same object would presumably save memory space. However, it would
> probably be good to update the comment to let people know that this will
> happen.
>
> What is the process for submitting suggested improvements to class comments?
>
> Cheers
> Andy

Henrik Sperre Johansen

Re: Is there a way to stop arrays sorting automatically?

In reply to this post by Ben Coman

Ben Coman wrote
> On 31 December 2017 at 04:00, Andy Burnett <

> andy.burnett@

> >
> wrote:
>
>> I suspect I am missing something very obvious, in which case could some
>> kind soul put me straight?
>>
>> I have the following code
>>
>> col := OrderedCollection new.
>> (1 to: 9) permutationsDo: [ :each | col add: (each )].
>>
>> I thought this would give me a collection containing all the
>> permutations.
>> However, what actually happens is that each of the arrays has been
>> 'magically' sorted back into numerical order. If I change the code to
>> read
>>
>> col := OrderedCollection new.
>> (1 to: 9) permutationsDo: [ :each | col add: (each asOrderedCollection
>> )].
>>
>> Then the permutations are retained. Is this how it is supposed to work?
>> Or, am I doing something wrong?
>>
>> Cheers
>> Andy
>>
>
>
> Its not so much that your first example sorted the permutations, but that
> the collection contained only one permutation.
> I've swapped the order of your examples and downsized them to the simplest
> case to observe.
> Something seems broken. It works as expected if the "copy" is
> uncommented.

It's not broken, but certainly deserves a comment as to why it operates
inline;
In the general case, one should not use/care about any given permutation
outside the block.
Allocating n! instances of an n-sized array by default, is a bad tradeoff
considering performance degradation for uses where n >> 3.
In the first case, a user can add a simple #copy, while in the second case,
a user would probably want/have to reimplement the method entirely.

Cheers,
Henry

--
Sent from: http://forum.world.st/Pharo-Smalltalk-Users-f1310670.html

Andy Burnett

Re: Is there a way to stop arrays sorting automatically?

In reply to this post by Andy Burnett

Henry said
>>>>

It's not broken, but certainly deserves a comment as to why it operates
inline;
In the general case, one should not use/care about any given permutation
outside the block.
Allocating n! instances of an n-sized array by default, is a bad tradeoff
considering performance degradation for uses where n >> 3.
In the first case, a user can add a simple #copy, while in the second case,
a user would probably want/have to reimplement the method entirely.
<<<

Thanks, that makes perfect sense. I will have a go at adding a suitable comment.

Cheers
Andy

Richard O'Keefe

Re: Is there a way to stop arrays sorting automatically?

I would check this in Pharo, but have so far failed to get it running under Ubuntu 17.10.

Squeak _is_ running there, sort of, and the definition of #permutationsDo: in Interval

is this code:

permutationsDo: aBlock

"Repeatly value aBlock with a single copy of the receiver. Reorder the copy

so that aBlock is presented all (self size factorial) possible permutations."

"(1 to: 4) permutationsDo: [:each | Transcript cr; show: each printString]"

self asArray permutationsDo: aBlock

Exactly the same comment is found in SequenceableCollections.

Are you sure that Pharo has something different? "with a SINGLE COPY of

the receiver" is pretty important. The thing is that the number of permutations

is so astronomically large that it really never makes sense to retain all of them

in memory. Suppose an array of n elements takes n+2 words, then holding

all of the permutations of 1..k would take (k+2)*k! + k! + 2 = k!(k+3)+2 words.

For k = 5 10 15 20 that's 962 47174402 23538138624002 55956746188062720002

words. If we assume a 64-bit laptop with 16 GiB of memory, k=12 is already too big.

Yet it is perfectly reasonable to iterate over all 12! permutations.

Another thing about iterating over permutations is that straightforward algorithms

take O(1) time per permutation, but not if you copy every time.

I don't think I've ever found a use for #permutationsDo: that didn't need to be

turned into a specialised backtracking algorithm with cutoffs pushed as early

as possible.

Prof. Andrew P. Black

Re: Is there a way to stop arrays sorting automatically?

+1 for what Richard says.

Moreover, if you know that n is small, and you really want copies of all th permutations, then adding a copy message to your block is really simple. But if the permutationsDo: method made the copy, then it would be useless except for very small values of n.

The comment that Richard quotes is in Pharo too. There is a good reason for the current behaviour, and it is documented.

Andy Burnett

Re: Is there a way to stop arrays sorting automatically?

In reply to this post by Andy Burnett

Richard wrote

>>>

I would check this in Pharo, but have so far failed to get it running under
Ubuntu 17.10.
Squeak _is_ running there, sort of, and the definition of #permutationsDo:
in Interval
is this code:

permutationsDo: aBlock
"Repeatly value aBlock with a single copy of the receiver. Reorder the copy
so that aBlock is presented all (self size factorial) possible
permutations."
"(1 to: 4) permutationsDo: [:each | Transcript cr; show: each printString]"

self asArray permutationsDo: aBlock

Exactly the same comment is found in SequenceableCollections.

Are you sure that Pharo has something different? "with a SINGLE COPY of
the receiver" is pretty important.

...

<<<

Thanks Richard. The Pharo comment is identical. The problem was simply that I hadn't understood what it was - quite clearly - telling me. Now that I understand the problem, the explanation makes perfect sense :-)

Cheers

Andy