[BitTorrent] Re: Really random?

shad0wmatt3r mgp at ucla.edu
Sun Jul 18 13:53:51 EDT 2004


Doh, I didn't realize that all indentation would be stripped from the
message... Which doesn't make Python code too readable. The code below
can also be found at http://www.bol.ucla.edu/~mgp/disk_manager.py if
anyone wants to take a look at it.

- Michael

--- In BitTorrent at yahoogroups.com, "shad0wmatt3r" <mgp at u...> wrote:
> Hi Arvid,
> 
> Quick question... Does this algorithm garuantee that by the time the
> nth piece comes in, that every piece received whose index is < n is
in
> its correct (final) position on the hard drive? I'm interested in an
> efficient way to maintain this invariant.
> 
> The simplest algorithm I could come up with that doesn't
pre-allocate
> the entire file before downloading and sorts as the file as it is
> written follows below. It does not, however, adhere to the invariant
> mentioned above -- on the average, it tends to do more sorting as
the
> file nears completion.
> 
> *** BEGIN PYTHON CODE ***
> 
> from random import shuffle
> 
> def addToFile(next_piece_index, next_piece):
> 	global completed_file, piece_map, pieces_completed, max_shifts
> 
> 	while next_piece_index < pieces_completed:
> 		old_piece_index = piece_map[next_piece_index]
> 		old_piece = completed_file[next_piece_index]
> 		piece_map[next_piece_index] = next_piece_index
> 		completed_file[next_piece_index] = next_piece
> 		next_piece_index = old_piece_index
> 		next_piece = old_piece
> 	
> 	piece_map[pieces_completed] = next_piece_index
> 	completed_file.append(next_piece)
> 	pieces_completed += 1
> 
> initial_file = 'abcdefghijklmnopqrstuvwxyz'
> piece_order = range(len(initial_file))
> shuffle(piece_order)
> 
> completed_file = []
> piece_map = [-1] * len(initial_file)
> pieces_completed = 0
> 
> for next_piece_index in piece_order:
> 	addToFile(next_piece_index, initial_file[next_piece_index])
> 
> print 'completed file = ' + ''.join(completed_file)
> 
> 
> *** END PYTHON CODE ***
> 
> Note that the "file" is just the string 'abcdefg
hijklmnopqrstuvwxyz',
> where each letter represents a piece.
> 
> Thanks,
> Michael
> 
> 
> > This is, roughly, the algorithm I employ in libtorrent, I'm pretty
> sure 
> > it's the same for all clients supporting this kind of storage.
> > 
> > storing a piece:
> > 
> > 1. let A be a newly downloaded piece, with index n
> > 2. let s be the number of slots allocated in the file we're
> >     downloading to. (the number of pieces it has room for)
> > 3. if n >= s then allocate a new slot and put the piece there
> > 4. if n < s then allocate a new slot, move the data at
> >     slot n to the new slot and put A in slot n
> > 
> > allocating a new slot:
> > 
> > 1. if there's an unassigned slot (a slot that doesn't
> >     contain any piece), return that slot index.
> > 2. append the new slot at the end of the file
> > 3. let i be the index of newly allocated slot
> > 4. if we have downloaded piece index i already (to slot j) then
> > 4.1. move the data at slot j to slot i
> > 4.2. return slot index j as the newly allocated free slot
> > 5. return i as the newly allocated slot
> > 
> > I wrote this from the top of my head, I may very well have
> forgotten 
> > something, feel free to correct any mistakes.
> > 
> > --
> > Arvid Norberg




------------------------ Yahoo! Groups Sponsor --------------------~--> 
Make a clean sweep of pop-up ads. Yahoo! Companion Toolbar.
Now with Pop-Up Blocker. Get it for free!
http://us.click.yahoo.com/L5YrjA/eSIIAA/yQLSAA/dkFolB/TM
--------------------------------------------------------------------~-> 

 
Yahoo! Groups Links

<*> To visit your group on the web, go to:
    http://groups.yahoo.com/group/BitTorrent/

<*> To unsubscribe from this group, send an email to:
    BitTorrent-unsubscribe at yahoogroups.com

<*> Your use of Yahoo! Groups is subject to:
    http://docs.yahoo.com/info/terms/
 



More information about the BitTorrent mailing list