Ad:

Python Discussion Thread
Unsolved
Views: 535

Sep 19th, 2009

Indexing two lists

Expand Post »

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...

python Syntax (Toggle Plain Text)
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
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!

Similar Threads

comparing lists in Python
Turn Off Indexing to Speed Up XP in Windows tips 'n' tweaks
Source code implementing Latent Semantic Indexing in C++
Domain Extensions - Does it make a difference in Search Engine Indexing? in Search Engine Optimization
Indexing in OS X 2 in Mac OS X

Benderbrau

Reputation Points: 10

Solved Threads: 0

Newbie Poster

Offline

13 posts
since Sep 2009

Permalink

Sep 19th, 2009

Re: Indexing two lists

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

 python Syntax (Toggle Plain Text)
>>> jobSize = [   5,    8,   3,   4,   1,    9,  7 ]
>>> length   = [ 500, 80, 300, 4, 10, 900, 70]
>>> 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

python Syntax (Toggle Plain Text)
>>> 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]
>>> 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]

Last edited by Gribouillis; Sep 19th, 2009 at 6:20 pm.

Gribouillis

Reputation Points: 930

Solved Threads: 668

Posting Maven

Offline

2,655 posts
since Jul 2008

Permalink

Sep 19th, 2009

Re: Indexing two lists

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

Benderbrau

Reputation Points: 10

Solved Threads: 0

Newbie Poster

Offline

13 posts
since Sep 2009

Permalink

Sep 19th, 2009

Re: Indexing two lists

Nice deduction indeed! Thanks Gribouillis!

vegaseat

Moderator

Reputation Points: 1333

Solved Threads: 1403

DaniWeb's Hypocrite

Offline

5,792 posts
since Oct 2004

Permalink

Sep 20th, 2009

Re: Indexing two lists

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.

AutoPython

Reputation Points: 14

Solved Threads: 17

Junior Poster

Offline

138 posts
since Sep 2009

Permalink

Sep 20th, 2009

Re: Indexing two lists

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

python Syntax (Toggle Plain Text)
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)
"""
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)
"""

Gribouillis

Reputation Points: 930

Solved Threads: 668

Posting Maven

Offline

2,655 posts
since Jul 2008

Permalink

Sep 20th, 2009

Re: Indexing two lists

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

sneekula

Reputation Points: 961

Solved Threads: 211

Nearly a Posting Maven

Offline

2,413 posts
since Oct 2006

Permalink

Sep 20th, 2009

Re: Indexing two lists

Click to Expand / Collapse Quote originally posted by sneekula ...

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

python Syntax (Toggle Plain Text)
def sorting_index(sequence):
    return list(zip(*sorted((y, x) for (x, y) in enumerate(sequence))))[1]
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

Last edited by Gribouillis; Sep 20th, 2009 at 1:04 pm.

Gribouillis

Reputation Points: 930

Solved Threads: 668

Posting Maven

Offline

2,655 posts
since Jul 2008

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.

Previous Thread in Python Forum Timeline: Mechanics of a python backend

Next Thread in Python Forum Timeline: Help a Novice with function please

DaniWeb Message

Cancel Changes

User Name
Password