The code to insert a value to a list indirectly ordered by an extra index list is useful by itself.
Python, 72 lines
Download
Copy to clipboard1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 | import random
from exceptions import ValueError
def indirectInsertion(F, ordering, x):
"""
Inserts x in F array ordered indirectly by ordering.
"""
L = len(ordering)
#Perform check,
if L != len(F):
raise ValueError
k = L-1
save = ordering[k] # index to space for x
while k >= 0 and x < F[ordering[k]]:
ordering[k] = ordering[k-1]
k -= 1
k = min(L-1, k+1)
# print "position to insert x", k
ordering[k] = save
F[save] = x
ordering[k] = save
if __name__ == "__main__":
#Example.
#Create random data array.
F = [random.random() for i in range(10)]
#Decorate, sort, undecorate
G = [(f, i) for i, f in enumerate(F)]
G.sort()
ordering = [g[1] for g in G]
print "Original data"
for i in range(len(F)):
print i, ordering[i], F[ordering[i]]
#Generate x to insert indirectly in array F.
x = random.random()
print "x to insert=", x
indirectInsertion(F, ordering, x)
for i in range(len(F)):
print i, ordering[i], F[ordering[i]]
When the program runs, it outputs
Original data
0 6 0.0495661645612
1 7 0.0716388504517
2 0 0.181165380138
3 3 0.193601438133
4 8 0.370737951412
5 1 0.409117107263
6 9 0.544771417861
7 5 0.640157511435
8 4 0.831191183469
9 2 0.861514272553
x to insert= 0.463842630209
0 6 0.0495661645612
1 7 0.0716388504517
2 0 0.181165380138
3 3 0.193601438133
4 8 0.370737951412
5 1 0.409117107263
6 2 0.463842630209
7 9 0.544771417861
8 5 0.640157511435
9 4 0.831191183469
|
The above code is easily distilled from a standard indirect version of the basic insertion sort algorithm. The avantage is that we don't move data list elements which might be of large size whereas we mostly manipulate small sized integer indices.
Tags: algorithms
I think you have a lot to learn about Python. Fundamentally, your "solution" is a bad idea, and I hope nobody (including yourself) uses it. I think you have a lot to learn about Python.
Python lists don't store the data itself, they store references. Integers are stored in Python as immutable objects. So your array of ints is really an array of references, just as your array of large data blobs is also an array of references. In other words: you are copying exactly the same amount of data when maintaining a sorted array of integers as you would maintaining a sorted array of large objects. So there is absolutely no point in maintaining this external "ordering" array.
Second, it is much faster to use Python facilities to do what needs doing than to laboriously write it out yourself. To insert an item in sorted order, you should at least use the "insert" method on an array to insert it into the correct place, rather than manually making room in the array as you have done. (More on this in a moment.)
Third, the sorting algorithms in Python are fantastically fast, and optimized (among other things) for sorting already-mostly-sorted lists. They cannot help but beat your awful O(n) search, which is so bad I wonder a little if you aren't trolling. So even adding the item to the end of the list, then calling sorted() on it, would be faster than what you've done.
Finally, with Python "the batteries are included"; Python comes with libraries to do many common tasks, including maintaining sorted arrays. Your entire recipe can--and should--be replaced with:
/larry/
p.s. instead of "for i in range(len(F))", try "for i, object in enumerate(F)".
I have to maintain more than one list ordered in my application.The F list may represent energy and another list may be cluster atom coordinates. I prefer the lists separate for ease of programming.