[freenet-cvs] r18678 - trunk/freenet/src/freenet/client/async

2008-03-21 Thread [email protected] 
Author: toad
Date: 2008-03-21 17:46:49 + (Fri, 21 Mar 2008)
New Revision: 18678

Modified:
   trunk/freenet/src/freenet/client/async/OfferedKeysList.java
Log:
Avoid the shuffling penalty.

Modified: trunk/freenet/src/freenet/client/async/OfferedKeysList.java
===
--- trunk/freenet/src/freenet/client/async/OfferedKeysList.java 2008-03-21 
17:16:24 UTC (rev 18677)
+++ trunk/freenet/src/freenet/client/async/OfferedKeysList.java 2008-03-21 
17:46:49 UTC (rev 18678)
@@ -31,7 +31,6 @@
 public class OfferedKeysList extends SendableRequest {

private final HashSet keys;
-   // FIXME is there any way to avoid the O(n) shuffling penalty here?
private final Vector keysList;
private static boolean logMINOR;
private final RandomSource random;
@@ -73,7 +72,11 @@
public Object chooseKey() {
// Pick a random key
if(keysList.isEmpty()) return null;
-   Key k = (Key) keysList.remove(random.nextInt(keysList.size()));
+   int ptr = random.nextInt(keysList.size());
+   // Avoid shuffling penalty by swapping the chosen element with 
the end.
+   Key k = (Key) keysList.get(ptr);
+   keysList.set(ptr, keysList.get(keysList.size()-1));
+   keysList.setSize(keysList.size()-1);
keys.remove(k);
return k;
}

[freenet-cvs] r18678 - trunk/freenet/src/freenet/client/async

2008-03-21 Thread toad 
Author: toad
Date: 2008-03-21 17:46:49 + (Fri, 21 Mar 2008)
New Revision: 18678

Modified:
   trunk/freenet/src/freenet/client/async/OfferedKeysList.java
Log:
Avoid the shuffling penalty.

Modified: trunk/freenet/src/freenet/client/async/OfferedKeysList.java
===
--- trunk/freenet/src/freenet/client/async/OfferedKeysList.java 2008-03-21 
17:16:24 UTC (rev 18677)
+++ trunk/freenet/src/freenet/client/async/OfferedKeysList.java 2008-03-21 
17:46:49 UTC (rev 18678)
@@ -31,7 +31,6 @@
 public class OfferedKeysList extends SendableRequest {
 
private final HashSet keys;
-   // FIXME is there any way to avoid the O(n) shuffling penalty here?
private final Vector keysList;
private static boolean logMINOR;
private final RandomSource random;
@@ -73,7 +72,11 @@
public Object chooseKey() {
// Pick a random key
if(keysList.isEmpty()) return null;
-   Key k = (Key) keysList.remove(random.nextInt(keysList.size()));
+   int ptr = random.nextInt(keysList.size());
+   // Avoid shuffling penalty by swapping the chosen element with 
the end.
+   Key k = (Key) keysList.get(ptr);
+   keysList.set(ptr, keysList.get(keysList.size()-1));
+   keysList.setSize(keysList.size()-1);
keys.remove(k);
return k;
}

___
cvs mailing list
[email protected]
http://emu.freenetproject.org/cgi-bin/mailman/listinfo/cvs