7 views

Skip to first unread message

Sep 7, 2005, 12:48:52 PM9/7/05

to

Given a list of N arbitrarily permutated integers from set {1..N}.

Need to find the ordering numbers of each integer in the LONGEST

increasing sequence to which this number belongs. Sample:

Need to find the ordering numbers of each integer in the LONGEST

increasing sequence to which this number belongs. Sample:

List:

[4, 5, 6, 1, 2, 7, 3]

Corresponding ordering numbers:

[1, 2, 3, 1, 2, 4, 3]

Details:

e.g. number 7 belongs to increasing sequence 1, 2, 7;

but this sequence is not the LONGEST sequence for "7".

The longest sequence for the 7 is 4, 5, 6, 7.

So, the 7's ordering number in this sequence is 4.

The salt of the thing is to do this with an O(n*log(n))

algorithm!

The straightforward O(n^2) algorithm is toooo slooow.

Any ideas?

Sep 7, 2005, 4:47:05 PM9/7/05

to

On 7 Sep 2005 09:48:52 -0700,

"n00m" <n0...@narod.ru> wrote:

"n00m" <n0...@narod.ru> wrote:

> Any ideas?

I wrote something like that for the Discrete Mathematics I took last

spring (we had to produce the longest sequence, though, rather than the

indexes into the original list, our list was not necessarily a

permutation of 1..N, and I "cheated" on the longest descending sequnce

by changing one of the comparison operators and re-running the program).

If push comes to shove, I suppose I could post the whole program (all

100 lines of it), but here's the comment near the top:

# consider that there are 2 ** n subsequences (corresponding to the 2 **

# n permutations of the original sequence); the trick is to accumulate

# them all at once while skipping the ones that are not strictly

# ascending and also pruning sequences that obviously can't "win"

It's not much to go on, but that bit after the ";" is the algorithm I

use. I can't tell you how fast it runs in big-O notation, but my old

500 MHz PowerMac G4 digested lists of tens or hundreds of thousands of

random integers while I waited.

Regards,

Dan

--

Dan Sommers

<http://www.tombstonezero.net/dan/>

Sep 7, 2005, 5:52:22 PM9/7/05

to

I coded a solution that can compute the ordering numbers for

random.shuffle(range(1, 1000001)) in 2.5 seconds (typical, Win 2K Pro,

Pentium 4 2.40GHz 785Meg RAM)

random.shuffle(range(1, 1000001)) in 2.5 seconds (typical, Win 2K Pro,

Pentium 4 2.40GHz 785Meg RAM)

Are you sure that this is not a homework problem?

Sep 8, 2005, 2:33:23 AM9/8/05

to

Thanks guys!

> Are you sure that this is not a homework problem?

... and let me reveal the secret:

http://spoj.sphere.pl/problems/SUPPER/

> Are you sure that this is not a homework problem?

http://spoj.sphere.pl/problems/SUPPER/

Hardly it can be easily reduced to "standard" LIS problem

(i.e. to find just a (any) Longest Increasing Sequence).

> I coded a solution that can compute the ordering numbers for

> random.shuffle(range(1, 1000001)) in 2.5 seconds (typical, Win 2K Pro,

> Pentium 4 2.40GHz 785Meg RAM)

Sounds very impressive! It would be great to see your py solution got

accepted on my link (yes! they accept Python 2.4.1 solutions! and of

course the registration is free and fully anonymous).

So far there is no any accepted Py solution for this problem (see

link "Best Solutions" on the top of page of this problem).

Note: their machines are PIII Xeon 700MHz (no limit. for memory usage).

PS Thanks, Dan! but frankly speaking I'm not much interested just

to get someone's ready-to-use code without understanding how it

works.

Sep 8, 2005, 12:25:25 PM9/8/05

to

> ... and let me reveal the secret:

> http://spoj.sphere.pl/problems /SUPPER/

> http://spoj.sphere.pl/problems /SUPPER/

your question is different than the question on this website.

also, what do you consider to be the correct output for this

permutation? (according to your original question)

[4, 5, 1, 2, 3, 6, 7, 8]

Manuel

Sep 8, 2005, 12:28:28 PM9/8/05

to

So, this has no real world use, aside from posting it on a website.

Thanks for wasting our time. You are making up an arbitrary problem and

asking for a solution, simply because you want to look at the

solutions, not because your problem needs to be solved. Clearly, this

is a waste of time.

Thanks for wasting our time. You are making up an arbitrary problem and

asking for a solution, simply because you want to look at the

solutions, not because your problem needs to be solved. Clearly, this

is a waste of time.

Sep 8, 2005, 12:54:42 PM9/8/05

to

Working on this allowed me to avoid some _real_ (boring) work at my

job.

job.

So clearly it served a very useful purpose! ;)

Manuel

Sep 8, 2005, 1:30:30 PM9/8/05

to pytho...@python.org

[sp1...@gmail.com]

If investigating algorithms irritates you, ignore it. The people

writing papers on this topic don't feel it's a waste of time. For

example,

http://citeseer.ist.psu.edu/bespamyatnikh00enumerating.html

"Enumerating Longest Increasing Subsequences and Patience Sorting (2000)"

Sergei Bespamyatnikh, Michael Segal

That's easy to follow, although their use of a Van Emde-Boas set as a

given hides the most challenging part (the "efficient data structure"

part).

Sep 8, 2005, 1:46:04 PM9/8/05

to

> That's easy to follow, although their use of a Van Emde-Boas set as a

> given hides the most challenging part (the "efficient data structure"

> part).

> given hides the most challenging part (the "efficient data structure"

> part).

The "efficient data structure" is the easy part.

Obviously, it is a dict of lists.

...or is it a list of dicts?...

...or is it a tuple of generators?...

Anyway, "being aware of the literature", "thinking", "being smart", and

"being Tim Peters" are all forms of cheating.

I prefer not to cheat. ;)

nOOm, I still need an answer...

Sep 8, 2005, 1:50:01 PM9/8/05

to

I don't think you're quite right.

We never know where we gain and where we lose.

We never know where we gain and where we lose.

> So clearly it served a very useful purpose! ;)

Thanks, Manuel!

> your question is different than the question on this website.

Not exactly so (maybe I'm wrong here). How I did it (but got TLE

- Time Limit Exceeded (which is 9 seconds)).

Firstly I find ordering numbers when moving from left to the right;

then I find ord. numbers for backward direction AND for DECREASING

subsequences:

4 5 1 2 3 6 7 8 << the list itself

1 2 1 2 3 4 5 6 << ordering numbers for forward direction

2 1 6 5 4 3 2 1 << ordering numbers for backward direction

===

3 3 7 7 7 7 7 7 << sums of the pairs of ord. numbers

Now those numbers with sum_of_ord.pair = max + 1 = 6 + 1

are the answer.

So the answer for your sample is: 1 2 3 6 7 8

Btw, I did it in Pascal. Honestly, I don't believe it can

be done in Python (of course I mean only the imposed time limit).

http://spoj.sphere.pl/status/SUPPER/

Message has been deleted

Sep 8, 2005, 4:05:03 PM9/8/05

to

> 4 5 1 2 3 6 7 8 << the list itself

> 1 2 1 2 3 4 5 6 << ordering numbers for forward direction

> 2 1 6 5 4 3 2 1 << ordering numbers for backward direction

> ===

> 3 3 7 7 7 7 7 7 << sums of the pairs of ord. numbers

Oops! Sorry for miscounting in backward direction.> 1 2 1 2 3 4 5 6 << ordering numbers for forward direction

> 2 1 6 5 4 3 2 1 << ordering numbers for backward direction

> ===

> 3 3 7 7 7 7 7 7 << sums of the pairs of ord. numbers

Should be (anyway the answer stays the same):

4 5 1 2 3 6 7 8 << the list itself

1 2 1 2 3 4 5 6 << ordering numbers for forward direction

5 4 6 5 4 3 2 1 << ordering numbers for backward direction

===

6 6 7 7 7 7 7 7 << sums of the pairs of ord. numbers

Sep 8, 2005, 9:31:52 PM9/8/05

to

n00m wrote:

> Firstly I find ordering numbers when moving from left to the right;

> then I find ord. numbers for backward direction AND for DECREASING

> subsequences:

Sounds good.

> Btw, I did it in Pascal. Honestly, I don't believe it can

> be done in Python (of course I mean only the imposed time limit).

> http://spoj.sphere.pl/status/SUPPER/

Is there a platform specified? Below is an alleged solution in Python.

--

--Bryan

#!/user/bin/env python

"""

Python 2.4 solution to:

http://spoj.sphere.pl/problems/SUPPER/

"""

from sys import stdin

def one_way(seq):

n = len(seq)

dominators = [n + 1] * (n * 1)

# dominators[j] is lowest final value of any increasing sequence of

# length j seen so far, as we left-right scan seq.

score = [None] * n

end = 0

for (i, x) in enumerate(seq):

# Binary search for x's place in dominators

low, high = 0, end

while high - low > 10:

mid = (low + high) >> 1

if dominators[mid] < x:

low = mid + 1

else:

high = mid + 1

while dominators[low] < x:

low += 1

dominators[low] = x

score[i] = low

end = max(end, low + 1)

return score

def supernumbers(seq):

forscore = one_way(seq)

opposite = [len(seq) - x for x in reversed(seq)]

backscore = reversed(one_way(opposite))

score = map(sum, zip(forscore, backscore))

winner = max(score)

return sorted([seq[i] for i in range(len(seq)) if score[i] == winner])

_ = stdin.readline()

sequence = [int(ch) for ch in stdin.readline().split()]

supers = supernumbers(sequence)

print len(supers)

for i in supers:

print i,

Message has been deleted

Sep 9, 2005, 3:00:49 AM9/9/05

to

Bravo, Bryan!

Looks very neat! (pity I can't give it a try in my Py 2.3.4

because of reversed() and sorted() functions)

And I've submitted it but got ... TLEs:

http://spoj.sphere.pl/status/SUPPER/

Funnily, the exec.time of the best C solution is only 0.06s!

Looks very neat! (pity I can't give it a try in my Py 2.3.4

because of reversed() and sorted() functions)

And I've submitted it but got ... TLEs:

http://spoj.sphere.pl/status/SUPPER/

Funnily, the exec.time of the best C solution is only 0.06s!

PS

In my 1st submission I overlooked that your code handles only

1 testcase (there are 10 of them); hence its 0.13s exec. time.

PPS

This is the code's text I submitted:

#!/user/bin/env python

from sys import stdin

for tc in range(10):

Sep 9, 2005, 4:50:39 AM9/9/05

to

n00m wrote:

> Bravo, Bryan!

> It's incredibly fast!

> Bravo, Bryan!

> It's incredibly fast!

Not compared to a good implementation for a compiled, low-level

language.

> But your code got WA (wrong answer).

> See my latest submission: http://spoj.sphere.pl/status/SUPPER/

> Maybe you slipped a kind of typo in it? Silly boundary cases?

Hmmm ... wrong answer ... what could ... ah! Here's a problem: I

bomb on the empty sequence. Correction below.

I'm not a perfect programmer, but I like to think I'm a good

programmer. Good programmers own their bugs.

If there's another problem, I need more to go on. From what you

write, I cannot tell where it fails, nor even what submission is

yours and your latest.

--

--Bryan

#!/user/bin/env python

"""

Python solution to:

http://spoj.sphere.pl/problems/SUPPER/

By Bryan Olson

"""

from sys import stdin

def one_way(seq):

n = len(seq)

dominators = [n + 1] * (n * 1)

score = [None] * n

end = 0

for (i, x) in enumerate(seq):

low, high = 0, end

while high - low > 10:

mid = (low + high) >> 1

if dominators[mid] < x:

low = mid + 1

else:

high = mid + 1

while dominators[low] < x:

low += 1

dominators[low] = x

score[i] = low

end = max(end, low + 1)

return score

def supernumbers(seq):

forscore = one_way(seq)

opposite = [len(seq) - x for x in reversed(seq)]

backscore = reversed(one_way(opposite))

score = map(sum, zip(forscore, backscore))

winner = max(score + [0])

Sep 9, 2005, 5:33:12 AM9/9/05

to

Oops Bryan... I've removed my reply that you refer to...

See my previous - CORRECT - reply. The code just times

out... In some sense it doesn't matter right or wrong is

its output.

Btw, what is the complexity of your algorithm?

Currently I'm at work and it's not easy for me to concentrate

on our subject.

See my previous - CORRECT - reply. The code just times

out... In some sense it doesn't matter right or wrong is

its output.

Btw, what is the complexity of your algorithm?

Currently I'm at work and it's not easy for me to concentrate

on our subject.

Sep 9, 2005, 5:45:12 AM9/9/05

to

> nor even what submission is yours and your latest.

Oops.. my UserName there is ZZZ.Submissions in the html table are ordered by date DESC.

Sep 9, 2005, 6:51:03 AM9/9/05

to

n00m wrote:

> Oops Bryan... I've removed my reply that you refer to...

> See my previous - CORRECT - reply. The code just times

> out... In some sense it doesn't matter right or wrong is

> its output.

> Oops Bryan... I've removed my reply that you refer to...

> See my previous - CORRECT - reply. The code just times

> out... In some sense it doesn't matter right or wrong is

> its output.

If my code times out, then they are using an archaic platform.

With respect to my code, you noted:

Bravo, Bryan! It's incredibly fast!

I myself did not claim 'incredibly fast'; but the code should

beat the 9-second mark on any currently-viable platform, even if

the machine were bought on special at Wal-Mart.

For this kind of low-level challenge, Python cannot compete with

the speed of C/C++, nor Ada, Pascal, ML, PL/1, nor even good

Java implementations. Nevertheless, even in the rare cases in

which efficiency of such computations is an issue, the Python

solution is usually worthy contender, and often the superior

solution.

Human time is more valuable than machine time. Python emphasizes

human-friendly code.

Alas, I would be (and, since I did cite it, was) wrong on that.

My code failed for the empty sequence. Wheter or not that was

one of the test cases, and whether or not it was a consideration

as the problem was defined, it was a bug. As I wrote:

Good programmers own their bugs.

> Btw, what is the complexity of your algorithm?

For a list of n items, time Theta(n ln(n)), space Theta(n).

--

--Bryan

Sep 9, 2005, 7:17:23 AM9/9/05

to

Oh!

Seems you misunderstand me!

See how the last block in your code should look:

Seems you misunderstand me!

See how the last block in your code should look:

for tc in range(10):

_ = stdin.readline()

sequence = [int(ch) for ch in stdin.readline().split()]

supers = supernumbers(sequence)

print len(supers)

for i in supers:

print i,

When I submitted it (for the 1st time) without

> for tc in range(10):

the e-judge counted the output of your code as

Wrong Answer; just because the e-judge got an answer

for only the very 1st testcase (I think in it was not

too large input data).

Sep 9, 2005, 1:29:29 PM9/9/05

to

n00m wrote:

> Oh!

> Seems you misunderstand me!

> See how the last block in your code should look:

>

> for tc in range(10):

> _ = stdin.readline()

> sequence = [int(ch) for ch in stdin.readline().split()]

> supers = supernumbers(sequence)

> print len(supers)

> for i in supers:

> print i,

> Oh!

> Seems you misunderstand me!

> See how the last block in your code should look:

>

> for tc in range(10):

> _ = stdin.readline()

> sequence = [int(ch) for ch in stdin.readline().split()]

> supers = supernumbers(sequence)

> print len(supers)

> for i in supers:

> print i,

Ah, I misunderstood the input. I thought they'd run it once for

each of their test cases. Handling exactly ten inputs sucks, so

how about:

while True:

if not stdin.readline().strip():

break

sequence = [int(ch) for ch in stdin.readline().split()]

supers = supernumbers(sequence)

print len(supers)

for i in supers:

print i,

--

--Bryan

Sep 9, 2005, 2:24:48 PM9/9/05

to

It also timed out:(

241056 2005-09-09 20:11:19 ZZZ time limit exceeded - 7064 PYTH

Btw, have a look at this nicest problem:

http://spoj.sphere.pl/problems/COINS/

My py solution takes #64 place among its best solutions:

Sep 9, 2005, 3:03:42 PM9/9/05

to

PS:

ALL problems in problems.PDF file (weekly updated):

ALL problems in problems.PDF file (weekly updated):

http://spoj.sphere.pl/problems.pdf

The friendliest online contester I've ever seen! JUST A NON-SUCH.

Sep 9, 2005, 6:25:51 PM9/9/05

to

n00m wrote:

> It also timed out:(

> It also timed out:(

Could be. Yet you did write:

> It's incredibly fast!

I never intended to submit this program for competition. The

contest ranks in speed order, and there is no way Python can

compete with truly-compiled languages on such low-level code.

I'd bet money that the algorithm I used (coded in C) can run

with the winners. I also think I'd wager that the Python version

outright trumps them on code size.

My first version bombed for the zero-length sequence. That was a

mistake, sorry, but it may not be one of their test-cases. I

wonder how many of the accepted entries would perform properly.

--

--Bryan

Sep 10, 2005, 4:52:24 AM9/10/05

to

Bryan Olson wrote:

> Could be. Yet you did write:

> > It's incredibly fast!

because I THOUGHT your first version handled ALL TEN

testcases from the input. But the code read from the

*20-lines* input *ONLY 2* its first lines.

Usually they place heavy data testcase(s) at the end

of the (whole) input. Like this:

3

2 3 1

7

4 5 6 1 2 7 3

...

...

...

100000

456 2 6789 ... ... ... ... ... 55444 1 ... 234

Surely producing an answer for list [2, 3, 1] will

be "incredibly fast" for ANY language and for ANY

algorithm.

> My first version bombed for the zero-length sequence. That was a

> mistake, sorry, but it may not be one of their test-cases.

In my turn I can bet there's not an empty sequence testcase in the

input.

> I

> wonder how many of the accepted entries would perform properly.

Info of such kind they keep in secret (along with what the input

data are).

One more thing.

They (the e-judge's admins) are not gods and they don't warrant

that if they put 9 sec timelimit for a problem then this problem

can be "solved" in all accepted languages (e.g. in Python).

> I never intended to submit this program for competition.

"Competition" is not quite relevant word here. It just LOOKS as

if it is a "regular" competetion. There nobody blames anybody.

Moreover, judging on my own experience, there nobody is even

interested in anybody. It's just a fun (but very useful fun).

Sep 10, 2005, 6:38:22 PM9/10/05

to

Bryan;

My own version also timed out.

And now I can tell: it's incredibly SLOW.

Nevertheless it would be interesting to compare

speed of my code against yours. I can't do it myself

because my Python is of 2.3.4 version.

My own version also timed out.

And now I can tell: it's incredibly SLOW.

Nevertheless it would be interesting to compare

speed of my code against yours. I can't do it myself

because my Python is of 2.3.4 version.

Just uncomment "your" part.

import bisect

def oops(w,a,b):

for m in w:

j=bisect.bisect_left(a,m)

a.insert(j,m)

b.insert(j,max(b[:j]+[0])+1)

def n00m(n,w):

a,b=[],[]

oops(w,a,b)

v=map(lambda x: -x, w[::-1])

c,d=[],[]

oops(v,c,d)

e=map(sum, zip(b, d[::-1]))

mx=max(e)

f=[]

for i in xrange(n):

if e[i]==mx:

f.append(i+1)

print len(f)

def b_olson(sequence):

supers = supernumbers(sequence)

print len(supers)

import random, time

n=50000

w=range(1,n+1)

random.shuffle(w)

t=time.time()

n00m(n,w)

print 'n00m:',time.time()-t

"""

t=time.time()

b_olson(w)

print 'b_olson:',time.time()-t

"""

Sep 10, 2005, 11:12:53 PM9/10/05

to pytho...@python.org

[Bryan Olson, on the problem at

http://spoj.sphere.pl/problems/SUPPER/

]

> I never intended to submit this program for competition. The

> contest ranks in speed order, and there is no way Python can

> compete with truly-compiled languages on such low-level code.

> I'd bet money that the algorithm I used (coded in C) can run

> with the winners. I also think I'd wager that the Python version

> outright trumps them on code size.

http://spoj.sphere.pl/problems/SUPPER/

]

> I never intended to submit this program for competition. The

> contest ranks in speed order, and there is no way Python can

> compete with truly-compiled languages on such low-level code.

> I'd bet money that the algorithm I used (coded in C) can run

> with the winners. I also think I'd wager that the Python version

> outright trumps them on code size.

Oh, it's not that bad <wink>. I took a stab at a Python program for

this, and it passed (3.44 seconds). It just barely made it onto the

list of "best" solutions, which I also guess is ranked by elapsed

runtime. The Java program right above it took 2.91 seconds, but ate

more than 27x as much RAM ;-)

I didn't make any effort to speed this, beyond picking a reasonable

algorithm, so maybe someone else can slash the runtime (while I

usually enjoy such silliness, I can't make time for it at present).

I'll include the code below.

Alas, without access to the input data they use, it's hard to guess

what might be important in their data. On my home box, chewing over

random 100,000-element permutations took less than a second each

(including the time to generate them); I'm pretty sure they're using

slower HW than mine (3.4 GHz P5).

> My first version bombed for the zero-length sequence. That was a

> mistake, sorry, but it may not be one of their test-cases. I

> wonder how many of the accepted entries would perform properly.

No idea here, and didn't even think about it.

Notes: the `all` returned by crack() is a list such that all[i] is

list of all (index, value) pairs such that the longest increasing

subsequence ending with `value` is of length i+1; `value` is at index

`index` in the input permutation. The maximal LISs thus end with the

values in all[-1]. findall() iterates backwards over `all`, to

accumulate all the values that appear in _some_ maximal LIS. There's

clearly wasted work in findall() (if someone is looking for an

algorithmic point to attack). Curiously, no use is made of that

values are integers, outside of input and output; any values with a

total ordering would work fine in crack() and findall().

"""

# http://spoj.sphere.pl/problems/SUPPER/

def crack(xs):

from bisect import bisect_right as find

smallest = []

all = []

n = 0

for index, x in enumerate(xs):

i = find(smallest, x)

if i == n:

smallest.append(x)

all.append([(index, x)])

n += 1

else:

all[i].append((index, x))

if x < smallest[i]:

smallest[i] = x

return all

def findall(all):

constraints = all[-1]

allints = [pair[1] for pair in constraints]

for i in xrange(len(all) - 2, -1, -1):

survivors = []

for pair in all[i]:

index, value = pair

for index_limit, value_limit in constraints:

if index < index_limit and value < value_limit:

survivors.append(pair)

allints.append(value)

break

constraints = survivors

return sorted(allints)

def main():

import sys

while 1:

n = sys.stdin.readline()

if not n:

break

n = int(n)

perm = map(int, sys.stdin.readline().split())

assert n == len(perm)

supers = findall(crack(perm))

perm = None # just to free memory

print len(supers)

print " ".join(map(str, supers))

if __name__ == "__main__":

main()

"""

Sep 11, 2005, 5:29:38 AM9/11/05

to

Tim Peters;

INCREDIBLE~

> 241433 2005-09-11 04:23:40 Tim Peters accepted 3.44 7096 PYTH

BRAVO!

I just wonder have I grey cells enough for to understand how your

algo works... and hopefully it's not your last solved problem on

the contester.

INCREDIBLE~

> 241433 2005-09-11 04:23:40 Tim Peters accepted 3.44 7096 PYTH

BRAVO!

I just wonder have I grey cells enough for to understand how your

algo works... and hopefully it's not your last solved problem on

the contester.

> I'm pretty sure they're using

> slower HW than mine (3.4 GHz P5).

As I mentioned before their 4 identical machines are PIII Xeon 700MHz.

PS:

each accepted solution automatically gets into "Best Solutions" list.

Sep 11, 2005, 1:37:01 PM9/11/05

to pytho...@python.org

[Tim Peters, on the problem at

http://spoj.sphere.pl/problems/SUPPER/

]

>> ...

http://spoj.sphere.pl/problems/SUPPER/

]

>> ...

> INCREDIBLE~

> 241433 2005-09-11 04:23:40 Tim Peters accepted 3.44 7096 PYTH

> BRAVO!

It's different now ;-) I added the two lines

import psyco

psyco.full()

and time dropped to 2.29, while memory consumption zoomed:

2005-09-11 18:44:57 Tim Peters accepted 2.29 42512 PYTH

That surprised me: my own test cases on Windows using Python 2.4.1

enjoyed the same order of speedup, but barely increased RAM usage.

Perhaps they installed an older (or newer <0.9 wink>) version of

psyco.

> I just wonder have I grey cells enough for to understand how your

> algo works...

You do! Work out some small examples by hand, and it will become

clear; be sure to read the comments before the code, because they

explain it.

> and hopefully it's not your last solved problem on the contester.

I have to stop now, else I wouldn't do anything else <0.3 wink>.

> ...

Sep 11, 2005, 7:43:15 PM9/11/05

to

Tim Peters wrote:

> [Bryan Olson, on the problem at

> http://spoj.sphere.pl/problems/SUPPER/

> ]

>

>>I never intended to submit this program for competition. The

>>contest ranks in speed order, and there is no way Python can

>>compete with truly-compiled languages on such low-level code.

>>I'd bet money that the algorithm I used (coded in C) can run

>>with the winners. I also think I'd wager that the Python version

>>outright trumps them on code size.

>

> Oh, it's not that bad <wink>. I took a stab at a Python program for

> this, and it passed (3.44 seconds).

[...]> [Bryan Olson, on the problem at

> http://spoj.sphere.pl/problems/SUPPER/

> ]

>

>>I never intended to submit this program for competition. The

>>contest ranks in speed order, and there is no way Python can

>>compete with truly-compiled languages on such low-level code.

>>I'd bet money that the algorithm I used (coded in C) can run

>>with the winners. I also think I'd wager that the Python version

>>outright trumps them on code size.

>

> Oh, it's not that bad <wink>. I took a stab at a Python program for

> this, and it passed (3.44 seconds).

> I didn't make any effort to speed this, beyond picking a reasonable

> algorithm, so maybe someone else can slash the runtime

Hmmm ... I used the Theta(n lg n) algorithm ... how the heck...

Aha! The 'bisect' module changed since last I looked. It still

has the Python implementation, but then the last few lines say:

# Overwrite above definitions with a fast C implementation

try:

from _bisect import bisect_right, bisect_left, insort_left,

insort_right, insort, bisect

except ImportError:

pass

Binary-search is the inner-loop in this algorithm. I wrote my

own binary-search, so I was executing Theta(n lg n) Python

statements. Tim's use of bisect means that his inner-loop is

in C, so he does Theta(n) Python statements and Theta(n lg n) C

statement.

The key to fast Python: use a good algorithm, and keep the inner

loop in C.

--

--Bryan

Sep 11, 2005, 8:39:09 PM9/11/05

to pytho...@python.org

[Tim Peters, on the problem at

http://spoj.sphere.pl/problems/SUPPER/

]

>> Oh, it's not that bad <wink>. I took a stab at a Python program for

>> this, and it passed (3.44 seconds).

>> ...

>> I didn't make any effort to speed this, beyond picking a reasonable

>> algorithm, so maybe someone else can slash the runtime

http://spoj.sphere.pl/problems/SUPPER/

]

>> Oh, it's not that bad <wink>. I took a stab at a Python program for

>> this, and it passed (3.44 seconds).

>> ...

>> I didn't make any effort to speed this, beyond picking a reasonable

>> algorithm, so maybe someone else can slash the runtime

[Bryan Olson]

> Hmmm ... I used the Theta(n lg n) algorithm ... how the heck...

> Aha! The 'bisect' module changed since last I looked. It still

> has the Python implementation, but then the last few lines say:

>

> # Overwrite above definitions with a fast C implementation

> try:

> from _bisect import bisect_right, bisect_left, insort_left, insort_right, insort, bisect

> except ImportError:

> pass

>

> Binary-search is the inner-loop in this algorithm. I wrote my

> own binary-search, so I was executing Theta(n lg n) Python

> statements. Tim's use of bisect means that his inner-loop is

> in C, so he does Theta(n) Python statements and Theta(n lg n) C

> statement.

That's part of it, but doesn't account for enough. If I disable the C

implementation of bisect (replace the "from ..." import above with a

"pass"), the program takes about 50% longer, which would still leave

it well under the 9-second SPOJ time limit. That's without psyco.

With psyco, it takes about the same time with the Python

implementation of bisect as with the C implementation.

Proably more important was my findall() routine. It does redundant

work, and its runtime seems hard to analyze, but it's conceptually

simple and actual timing showed it takes about a third of the time

consumed by my crack() on random 100,000-element permutations. In

fact, findall() takes very close to the amount of time needed just to

read a giant line of input and convert it to a list of ints (without

psyco; with psyco converting the input takes longer than findall()).

Possible surprise: there's a simple trick that allows rewriting

findall() to produce the result list in sorted order directly, instead

of building it in "random" order and sorting it at the end. That made

no measurable difference.

> The key to fast Python: use a good algorithm,

Absolutely!

> and keep the inner loop in C.

Usually ;-)

Add another: especially for long-term maintenance, readability,

stability and performance, use a library function instead of rolling

your own. The chance that Raymond Hettinger is going to recode _your_

functions in C is approximately 0 ;-)

Sep 14, 2005, 12:29:03 PM9/14/05

to

Tim Peters wrote:

> The chance that Raymond Hettinger is going to recode _your_

> functions in C is approximately 0 ;-)

Sep 14, 2005, 1:17:09 PM9/14/05

to

Sep 14, 2005, 1:32:51 PM9/14/05

to

Got it! He is a kind of pythonic monsters.

Btw, why it's impossible to reply to old threads?

Namely, there're no more "Reply" link in them.

Only "Reply to author" etc.

Sep 14, 2005, 2:56:53 PM9/14/05

to pytho...@python.org

"n00m" <n0...@narod.ru> wrote in message

news:1126715343....@f14g2000cwb.googlegroups.com...

> Who is Raymond Hettinger?

The Python developer who, in the last few years, has perhaps been the most

active in coding or recoding library modules, such as itertools and sets,

in C. He also partipates in development discussions, helps with

SourceForge tracker items (RFEs, bugs, and patches) and occasionally posts

here, especially about his modules, for which he is the expert.

Terry J. Reedy

Sep 14, 2005, 4:42:31 PM9/14/05

to

Perhaps because you are not using a real Usenet client?

Reinhold

Sep 15, 2005, 2:17:26 AM9/15/05

to

Thank you both for your replies.

And my personal "Thank you!" to Mr. Hettinger for

all his tremendous work!

And my personal "Thank you!" to Mr. Hettinger for

all his tremendous work!

> Perhaps because you are not using a real Usenet client?

Yes! And I don't even know what is the beast - Usenet client.

I just keep in Favorites of my browser (IE 6.0) this link:

http://groups.google.com/group/comp.lang.python/

Sep 15, 2005, 1:39:19 PM9/15/05

to

I hope nobody have posted similar solution (it's tested, but I didn't

submit it to contest):

submit it to contest):

from bisect import bisect_right as find

def supernumbers(ls):

indices = [0]*len(ls)

for i, e in enumerate(ls):

indices[e - 1] = i

result = [None]*len(ls)

borders = []

for i in indices:

ind = find(borders, i)

result[i] = ind + 1

if ind == len(borders):

borders.append(i)

else:

borders[ind] = i

return result

At least, it looks shorter than other solutins.

Of course, it allows number of optimizations like

prefetching length and caching borders.append.

If I'm correct, it takes O(n*log (max sequence length)) time that can

be a win for huge datasets.

With the best regards,

anton.

Sep 16, 2005, 12:51:35 PM9/16/05

to

Anton,

it simply does not work! Try supernumbers([2,1,4,5,3]).

Sep 26, 2005, 7:59:27 AM9/26/05

to

Hellom n00m!

I beg your pardon for not having replied for such long time---I was

really busy.

Yes, the posted code doesn't solve the supernumbers problem, but solves

the problem you posted first as I understood it :) --- for each number

find a position of this number in the longest sequence it belongs to.

Ok, anyway, I hope that I can suggest a solution to the supernumbers

problem (see below).

Actually, as I find out today testing it against Tim Peters's solution,

they are of the same kind, but I use one additional optimimization.

And the last note: I didn't persue the maximal performace, rather

clarity of the algorithm.

With the best regards,

anton.

from bisect import bisect as find

def supernumbers(l):

indices = [0]*len(l)

for i, e in enumerate(l):

indices[e - 1] = i

# Now we can find out index of each element in the longest ascending

sequence it belongs to

# I call this index 'generation'

# ess is an array indexed by generations and holding

# ascending list of generation's elements

# Note: suffix s stands for a list, therefore ess---list of lists

of elements

# Note: ess holds not the elements itself, but elements decreased

by 1

ess = []

# Borders i.e. positions that separate generations

borders = []

for e, i in enumerate(indices):

ind = find(borders, i)

if ind < len(borders):

borders[ind] = i

ess[ind].append(e)

else:

borders.append(i)

ess.append([e])

# Now we should filter out those elements that don't

# belong to the longest sequences

gens = reversed(ess) # walk generations in reverse order

fes = gens.next() # fes stands for elements' filter

r = fes # r is a list of supernumbers; obvioulsy all the elements of

the latest generation belong to r

for es in gens:

new_fes = []

s = 0 # As elements are sorted ascendingly we can check lesser and

lesser lists

for e in es:

s = find(fes, e, s)

if s == len(fes):

# There is no more elements in filter that are greater

# than elements in the current generation

break

if indices[fes[s]] > indices[e]: # Nice---element e belongs to

the longest sequence

new_fes.append(e)

# Note: the following invariant holds: len(new_fes) > 0

fes = new_fes

r += new_fes

return [e + 1 for e in r] # As we used numbers from 0 internally

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu