fork download
copy 
  1. import java.util.ArrayList;
  2. import java.util.PriorityQueue;
  3. import java.util.Random;
  4. import java.util.Scanner;
  5.  
  6. public class Main {
  7.  
  8. 	public static void main(String[] args) {
  9. 		final int N = 500000;
  10. 		Random rnd = new Random(42);
  11. 		ArrayList<Long> values = new ArrayList<>();
  12. 		for (int i = 0; i < N; ++i) {
  13. 			long v = rnd.nextInt(Integer.MAX_VALUE) * (1L << 32) + rnd.nextInt(Integer.MAX_VALUE);
  14. 			values.add(v);
  15. 		}
  16. 		System.out.println("uniform distribution");
  17. 		benchmark(values);
  18. 		System.out.println();
  19.  
  20. 		values.clear();
  21. 		for (int i = 0; i < N; ++i) {
  22. 			long v = (long) Math.exp(rnd.nextDouble() * 40 + 1);
  23. 			values.add(v);
  24. 		}
  25. 		System.out.println("exponential distribution");
  26. 		benchmark(values);
  27. 	}
  28.  
  29. 	static void benchmark(ArrayList<Long> values) {
  30. 		{
  31. 			long startTime = System.currentTimeMillis();
  32. 			RadixHeap q = new RadixHeap();
  33. 			for (int i = 0; i < values.size(); ++i) {
  34. 				q.push(values.get(i));
  35. 			}
  36. 			ArrayList<Long> popped = new ArrayList<>(values.size());
  37. 			while (q.size() > 0) {
  38. 				popped.add(q.pop());
  39. 			}
  40. 			System.out.println("RadixHeap:" + (System.currentTimeMillis() - startTime));
  41. 		}
  42. 		{
  43. 			long startTime = System.currentTimeMillis();
  44. 			PriorityQueue<Long> q = new PriorityQueue<>();
  45. 			for (int i = 0; i < values.size(); ++i) {
  46. 				q.add(values.get(i));
  47. 			}
  48. 			ArrayList<Long> popped = new ArrayList<>(values.size());
  49. 			while (q.size() > 0) {
  50. 				popped.add(q.poll());
  51. 			}
  52. 			System.out.println("PriorityQueue:" + (System.currentTimeMillis() - startTime));
  53. 		}
  54.  
  55. 		// verify
  56. 		//		Collections.sort(values);
  57. 		//		System.out.println(poped.equals(values));
  58. 	}
  59.  
  60. 	static class RadixHeap {
  61. 		private ArrayList<ArrayList<Long>> buf = new ArrayList<>();
  62. 		private long last = 0;
  63. 		private int size = 0;
  64.  
  65. 		RadixHeap() {
  66. 			for (int i = 0; i <= 64; ++i) {
  67. 				buf.add(new ArrayList<Long>());
  68. 			}
  69. 		}
  70.  
  71. 		void push(long v) {
  72. 			assert (last <= v);
  73. 			++size;
  74. 			buf.get(bsr(v ^ last)).add(v);
  75. 		}
  76.  
  77. 		long pop() {
  78. 			if (buf.get(0).isEmpty()) {
  79. 				int pos = 1;
  80. 				while (buf.get(pos).isEmpty()) {
  81. 					++pos;
  82. 				}
  83. 				long nextLast = Long.MAX_VALUE;
  84. 				for (int i = 0; i < buf.get(pos).size(); ++i) {
  85. 					nextLast = Math.min(nextLast, buf.get(pos).get(i));
  86. 				}
  87. 				for (long move : buf.get(pos)) {
  88. 					buf.get(bsr(move ^ nextLast)).add(move);
  89. 				}
  90. 				last = nextLast;
  91. 				buf.get(pos).clear();
  92. 			}
  93. 			--size;
  94. 			buf.get(0).remove(buf.get(0).size() - 1);
  95. 			return last;
  96. 		}
  97.  
  98. 		int size() {
  99. 			return this.size;
  100. 		}
  101.  
  102. 		static int bsr(long v) {
  103. 			return 64 - Long.numberOfLeadingZeros(v);
  104. 		}
  105. 	}
  106. }
  107.  
Success #stdin #stdout 3.75s 320448KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
uniform distribution
RadixHeap:919
PriorityQueue:933

exponential distribution
RadixHeap:625
PriorityQueue:941
https://ideone.com/BVQI86
language:
Java (HotSpot 12)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!