Indexing two lists

[Benderbrau]

Hello, I'm posting this code so that maybe it will help someone else in the future. I spent about a week trying to figure this out, and Google searches were not helping. Hopefully anyone else wondering about this will see this post on a Google result.

The program I finished writing was to simulate memory allocation, using schemes called first fit and best fit. I had two lists: jobSize (how big the job was) and length (how long the job stays active). For best fit, you must sort the job sizes, and I was having trouble keeping track with which item in the length list went to which jobSize item.

Anyway, if that made sense, here's what I did to sort the length list according to how the jobSize list was sorted...

sortJobSize = sorted(jobSize)
a=0
while a<len(length):
     n=0	
     while n < len(length):
          if jobSize[n] == sortJobSize[a]:
               length[a] = length[n]
          n+=1
     a+=1

As you can see, it's very simple and I'm amazed it took me so long to hammer out a working algorithm. Basically, it will take one item from jobSize at a time and compare it to each item in the sorted list. For every item that matches, it will change the location of length's item according to the index of sortJobSize. Hope this helps someone!

[Gribouillis]

This kind of problem has already been posted in this forum. I call this "sorting by colums".
Suppose we have 2 lists

>>> jobSize = [   5,    8,   3,   4,   1,    9,  7 ]
>>> length   = [ 500, 80, 300, 4, 10, 900, 70]

how to sort the first list and update the second list according to this sort ? There is a trick for this

>>> L = zip(*sorted(zip(tuple(jobSize), tuple(length))))
>>> sortJobSize, length = (list(t) for t in L)
>>> sortJobSize
[1, 3, 4, 5, 7, 8, 9]
>>> length
[10, 300, 4, 500, 70, 80, 900]

[Benderbrau]

Awesome, thanks! I tried something similar, but never got it working.

[vegaseat]

Nice deduction indeed! Thanks Gribouillis!

[AutoPython]

Wow! So is that one of those things you just have learn by memory? I kind of like Benderbrau's though because it's more readable and you can actually see what's going on. But Gribouillis' way is very efficient and mind boggling.

[Gribouillis]

An interesting variation on this is to write a function to generate a "sorting index":

def sorting_index(sequence):
    return zip(*sorted((y, x) for (x, y) in enumerate(sequence)))[1]

if __name__ == "__main__":
    jobSize = [5, 8, 3, 4, 1, 9, 7]
    length = [ 500, 80, 300, 4, 10, 900, 70]

    index = sorting_index(jobSize)
    print("job sizes: {0}".format(jobSize))
    print("lengths: {0}".format(length))
    print("sorted job sizes: {0}".format([jobSize[i] for i in index]))
    print("updated lengths: {0}".format([length[i] for i in index]))
    print("index: {0}".format(index))

""" my output --->
job sizes: [5, 8, 3, 4, 1, 9, 7]
lengths: [500, 80, 300, 4, 10, 900, 70]
sorted job sizes: [1, 3, 4, 5, 7, 8, 9]
updated lengths: [10, 300, 4, 500, 70, 80, 900]
index: (4, 2, 3, 0, 6, 1, 5)
"""

[sneekula]

Nice, looks like Python3 has bit your fancy.
Sooner or later we all have to follow your example.

[Gribouillis]

Nice, looks like Python3 has bit your fancy.
Sooner or later we all have to follow your example.

In fact, the above code doesn't run with python 3. You must modify the function like this

def sorting_index(sequence):
    return list(zip(*sorted((y, x) for (x, y) in enumerate(sequence))))[1]

because zip doesn't return a list in 3.1 :)