fast python input

[evan]

So for my algorithms class we need to program in a new language this week (i've been using java because I know it best...) and I've decided to do python. My algorithm is getting seriously slowed down by the sheer number of numbers I have to read from standard input...

what's the fastest way to read in a bunch of integers into an array? The max input is 10^5 different numbers.

[Kickaha]

That depends on where they're coming from, and how they're formatted.

File? One per line? Tab delimited? Standard input?

[evan]

standard input, here's an example...

5 2 7 3 9 1
5 7 2 3 9 1
0


the first number on a line is the # of numbers, the rest go in the array. 0 marks the end of input.

[Kickaha]

Well if you'd *type faster*...

;)

off the top of my head...


arrays = []
lines = sys.stdin.read()
for line in lines:
elements = line.split()
if len(elements) > 1:
arrays.append(elements)[1:])


Just builds the arrays by skipping the first element completely.

[evan]

do arrays in python not have a fixed size? for 10^5 numbers reallocating the array frequently could get kinda costly, right?

err.... nevermind, I actually read the code now hehehe

[Kickaha]

Oh wait, these all go into *ONE* array? What I gave you makes an array of arrays, one for each line.

To make one array with all the numbers, change the append to extend.

[evan]

Well if any of you want a little brainteaser here is the main point of my homework assignment for algorithms. There's a story behind it but this is what it boils down to:

given a list, count how many "swaps" would be required to sort it with bubblesort... in O(nlogn) time. (so you can't just bubble sort it and count the swaps)

my best guess before hearing the efficiency restriction was to go through the unsorted list, and for each number count the numbers before it that are greater and the numbers after it that are less. the total of all these counts is 2x the number of swaps (or at least it was in my test cases). Doesn't require any sorting... but still O(n^2) because for every number in the list it runs through the entire list. damn, oh well.



anyway, if you choose to click on the spoiler the homework is due for me friday night at midnight, US eastern time, so you can post your solutions after that :) Until then I'll keep working, and if python is giving me any more issues I'll probably post here if I can't effectively google my way to an answer (edit: to the python troubles, not the assignment as a whole)


oh, which reminds me: what kind of sort does pythons .sort() method use? / what's it's big O? I would assume a mergesort or quicksort...

[evan]

ok so going back to my n^2 way of thinking about it I think it also works if you just go through the list one way... meaning look at the unsorted list, for element n, go through the rest of the list (only the part after n), and add a counter for numbers that are less than it and to the right. you can ignore the left. then you're left with the number of necessary swaps. I think. It is bordering on 4:00am so I might not be thinking right, and my original thought in the above post might have been erroneous... oh well. pretty sure this still counts as O(n^2) :(

[billybobsky]

ok so going back to my n^2 way of thinking about it I think it also works if you just go through the list one way... meaning look at the unsorted list, for element n, go through the rest of the list (only the part after n), and add a counter for numbers that are less than it and to the right. you can ignore the left. then you're left with the number of necessary swaps. I think. It is bordering on 4:00am so I might not be thinking right, and my original thought in the above post might have been erroneous... oh well. pretty sure this still counts as O(n^2) :(
factorial time actually...

python sort uses timsort which is a hybrid of merge and insert (evidently)...

[evan]

well i think i found a way to do it by making a few additions to mergesort (to count up the "swaps"). It works for all the test cases and ones that I make up but still fails on the automatic grader (only response i get: "wrong answer"). aaahhhhhhh. if/when I get it working I'll post it so that those following along at home can see ;)

thanks for the help so far guys.

[evan]

alright... turns out the python running for the grading software is version 2.6.5 and I'm running 2.7, which I've been told may cause problems. Is there a way for me to run in 2.6.5 through terminal on my computer?

[Kickaha]

Hmm. As long as you don't use any 2.7 specific features, you should be fine, unless there are bugs I'm unaware of.

Specifically, yes, you can go grab a full Python 2.6.5 installation from fink or darwinports, but... here's my /usr/bin/py*:

/usr/bin/pydoc* /usr/bin/python* /usr/bin/python2.5-config@ /usr/bin/pythonw*
/usr/bin/pydoc2.5@ /usr/bin/python-config* /usr/bin/python2.6@ /usr/bin/pythonw2.5@
/usr/bin/pydoc2.6@ /usr/bin/python2.5@ /usr/bin/python2.6-config@ /usr/bin/pythonw2.6@


See if you have something similar to choose from.

[evan]

got it!! Turns out my issue wasn't versions but the automatic grader needed a file main.py, and I kept submitting Main.py. wooo!!!!

here's the code (spoiler tags didn't work on it). Basically key was when merging, how could you consistently tell how many swaps were needed to get a number into the same sorted list? Turns out it was just the number of items in the left array it had to "pass up" to get to the correct spot in the sorted array. woo!

**code removed until it's after the due date... honor code stuff. small chance someone would find this but still can't take it**