Adds `[Heap]PriorityQueue.of` constructor. (#734) Introduces efficient (linear-number of comparisons) "heapify" algorithm for converting an unsorted list to a heap-sorted list, using it for the of constructor, and after a large addAll operation, when it's presumed faster than just bubbling down all the new elements. Also rewrites HeapPriorityQueue to use a growable list as backing array, instead of implementing the same thing using the double-when-full algorithm, and still having to deal with nullable cells. The platform growable list implementation is assumed to efficiently avoid some of those null checks.
diff --git a/pkgs/collection/CHANGELOG.md b/pkgs/collection/CHANGELOG.md index 0123f87..5164fca 100644 --- a/pkgs/collection/CHANGELOG.md +++ b/pkgs/collection/CHANGELOG.md
@@ -5,6 +5,10 @@ `Map.entries`. - Explicitly mark `BoolList` as `abstract interface` - Address diagnostics from `strict_top_level_inference`. +- Optimize equality and hash code for maps by using `update` and a `values` + iterator to avoid extra lookups. +- Add `PriorityQueue.of` constructor and optimize adding many elements. +- Address diagnostics from `strict_top_level_inference`. ## 1.19.1
diff --git a/pkgs/collection/lib/src/priority_queue.dart b/pkgs/collection/lib/src/priority_queue.dart index 11b0348..df5b43b 100644 --- a/pkgs/collection/lib/src/priority_queue.dart +++ b/pkgs/collection/lib/src/priority_queue.dart
@@ -22,9 +22,9 @@ /// always give equal objects the same priority, /// otherwise [contains] or [remove] might not work correctly. abstract class PriorityQueue<E> { - /// Creates an empty [PriorityQueue]. + /// Creates an empty priority queue. /// - /// The created [PriorityQueue] is a plain [HeapPriorityQueue]. + /// The created `PriorityQueue` is a plain [HeapPriorityQueue]. /// /// The [comparison] is a [Comparator] used to compare the priority of /// elements. An element that compares as less than another element has @@ -36,6 +36,20 @@ factory PriorityQueue([int Function(E, E)? comparison]) = HeapPriorityQueue<E>; + /// Creates a new [HeapPriorityQueue] containing [elements]. + /// + /// The [comparison] is a [Comparator] used to compare the priority of + /// elements. An element that compares as less than another element has + /// a higher priority. + /// + /// Unlike [PriorityQueue.new], the [comparison] cannot be omitted. + /// If the elements are comparable to each other, use [Comparable.compare] + /// as the comparison function, or use a more specialized function + /// if one is available. + factory PriorityQueue.of( + Iterable<E> elements, int Function(E, E) comparison) = + HeapPriorityQueue<E>.of; + /// Number of elements in the queue. int get length; @@ -151,45 +165,41 @@ /// /// The elements are kept in a heap structure, /// where the element with the highest priority is immediately accessible, -/// and modifying a single element takes -/// logarithmic time in the number of elements on average. +/// and modifying a single element takes, on average, +/// logarithmic time in the number of elements. /// /// * The [add] and [removeFirst] operations take amortized logarithmic time, -/// O(log(n)), but may occasionally take linear time when growing the capacity -/// of the heap. -/// * The [addAll] operation works as doing repeated [add] operations. +/// O(log(*N*)) where *N* is the number of elements, but may occasionally +/// take linear time when growing the capacity of the heap. +/// * The [addAll] operation works by doing repeated [add] operations. +/// May be more efficient in some cases. /// * The [first] getter takes constant time, O(1). /// * The [clear] and [removeAll] methods also take constant time, O(1). /// * The [contains] and [remove] operations may need to search the entire -/// queue for the elements, taking O(n) time. -/// * The [toList] operation effectively sorts the elements, taking O(n*log(n)) -/// time. +/// queue for the elements, taking O(*N*) time. +/// * The [toList] operation effectively sorts the elements, +/// taking O(n * log(*N*)) time. /// * The [toUnorderedList] operation copies, but does not sort, the elements, /// and is linear, O(n). -/// * The [toSet] operation effectively adds each element to the new set, taking -/// an expected O(n*log(n)) time. +/// * The [toSet] operation effectively adds each element to the new +/// [SplayTreeSet], taking an expected O(n * log(*N*)) time. +/// +/// The [comparison] function is used to order elements, with earlier elements +/// having higher priority. That is, elements are extracted from the queue +/// in ascending [comparison] order. +/// If two elements have the same priority, their ordering is unspecified +/// and may be arbitrary. class HeapPriorityQueue<E> implements PriorityQueue<E> { - /// Initial capacity of a queue when created, or when added to after a - /// [clear]. - /// - /// Number can be any positive value. Picking a size that gives a whole - /// number of "tree levels" in the heap is only done for aesthetic reasons. - static const int _initialCapacity = 7; - /// The comparison being used to compare the priority of elements. - final Comparator<E> comparison; + final int Function(E, E) comparison; /// List implementation of a heap. - List<E?> _queue = List<E?>.filled(_initialCapacity, null); - - /// Number of elements in queue. - /// - /// The heap is implemented in the first [_length] entries of [_queue]. - int _length = 0; + List<E> _queue; /// Modification count. /// /// Used to detect concurrent modifications during iteration. + /// Incremented whenever an element is added or removed. int _modificationCount = 0; /// Create a new priority queue. @@ -202,31 +212,72 @@ /// is the case, `E` must implement [Comparable], and this is checked at /// runtime for every comparison. HeapPriorityQueue([int Function(E, E)? comparison]) - : comparison = comparison ?? defaultCompare; + : comparison = comparison ?? defaultCompare, + _queue = <E>[]; - E _elementAt(int index) => _queue[index] ?? (null as E); + /// Creates a new priority queue containing [elements]. + /// + /// The [comparison] is a [Comparator] used to compare the priority of + /// elements. An element that compares as less than another element has + /// a higher priority. + HeapPriorityQueue.of(Iterable<E> elements, this.comparison) + : _queue = elements.toList() { + _heapify(); + } + + /// Converts an unordered list of elements to a heap-ordered list of elements. + /// + /// Does so by ordering sub-trees iteratively, then bubbling their parent + /// down into the two ordered subtrees. + /// Trivially ignores the last half of elements, which have no children. + /// Does a number of bubble-down steps that is bounded by the number + /// of elements. Each bubble-down step does two comparisons. + void _heapify() { + // Last non-leaf node's index, negative for empty or one-element queue. + var cursor = _queue.length ~/ 2 - 1; + while (cursor >= 0) { + _bubbleDown(_queue[cursor], cursor); + cursor -= 1; + } + } @override void add(E element) { _modificationCount++; - _add(element); + _queue.add(element); + _bubbleUp(element, _queue.length - 1); } @override void addAll(Iterable<E> elements) { - var modified = 0; - for (var element in elements) { - modified = 1; - _add(element); + var endIndex = _queue.length; + _queue.addAll(elements); + var newLength = _queue.length; + var addedCount = newLength - endIndex; + if (addedCount == 0) return; + _modificationCount++; + // Approximation for when the time to bubble up all added elements, + // taking approx. addedCount * (log2(newLength)-1) comparisons worst-case, + // (bubble-up does one comparison per element per level), + // is slower than just heapifying the entire heap, which does + // newLength * 2 comparisons worst-case. + // Uses `endIndex.bitLength` instead of `newLength.bitLength` because + // if `addedCount` is greater than `newLength`, the bitLength won't matter + // for any non-trivial heap, and if not, every added element is a leaf + // element, so it only has to look at log2(endIndex) parents. + if (addedCount * endIndex.bitLength >= newLength * 2) { + _heapify(); + return; } - _modificationCount += modified; + for (var i = endIndex; i < newLength; i++) { + _bubbleUp(_queue[i], i); + } } @override void clear() { _modificationCount++; - _queue = const []; - _length = 0; + _queue.clear(); } @override @@ -243,27 +294,24 @@ Iterable<E> get unorderedElements => _UnorderedElementsIterable<E>(this); @override - E get first { - if (_length == 0) throw StateError('No element'); - return _elementAt(0); - } + E get first => _queue.first; @override - bool get isEmpty => _length == 0; + bool get isEmpty => _queue.isEmpty; @override - bool get isNotEmpty => _length != 0; + bool get isNotEmpty => _queue.isNotEmpty; @override - int get length => _length; + int get length => _queue.length; @override bool remove(E element) { var index = _locate(element); if (index < 0) return false; _modificationCount++; - var last = _removeLast(); - if (index < _length) { + var last = _queue.removeLast(); + if (index < _queue.length) { var comp = comparison(last, element); if (comp <= 0) { _bubbleUp(last, index); @@ -276,27 +324,25 @@ /// Removes all the elements from this queue and returns them. /// - /// The returned iterable has no specified order. - /// The operation does not copy the elements, - /// but instead keeps them in the existing heap structure, - /// and iterates over that directly. + /// The [HeapPriorityQueue] returns a [List] of its elements, + /// with no guaranteed order. + /// + /// If the elements are not needed, use [clear] instead. @override - Iterable<E> removeAll() { + List<E> removeAll() { _modificationCount++; var result = _queue; - var length = _length; - _queue = const []; - _length = 0; - return result.take(length).cast(); + _queue = <E>[]; + return result; } @override E removeFirst() { - if (_length == 0) throw StateError('No element'); + if (_queue.isEmpty) throw StateError('No element'); _modificationCount++; - var result = _elementAt(0); - var last = _removeLast(); - if (_length > 0) { + var result = _queue.first; + var last = _queue.removeLast(); + if (_queue.isNotEmpty) { _bubbleDown(last, 0); } return result; @@ -306,34 +352,19 @@ List<E> toList() => _toUnorderedList()..sort(comparison); @override - Set<E> toSet() { - var set = SplayTreeSet<E>(comparison); - for (var i = 0; i < _length; i++) { - set.add(_elementAt(i)); - } - return set; - } + Set<E> toSet() => SplayTreeSet<E>(comparison)..addAll(_queue); @override List<E> toUnorderedList() => _toUnorderedList(); - List<E> _toUnorderedList() => - [for (var i = 0; i < _length; i++) _elementAt(i)]; + List<E> _toUnorderedList() => _queue.toList(); /// Returns some representation of the queue. /// /// The format isn't significant, and may change in the future. @override String toString() { - return _queue.take(_length).toString(); - } - - /// Add element to the queue. - /// - /// Grows the capacity if the backing list is full. - void _add(E element) { - if (_length == _queue.length) _grow(); - _bubbleUp(element, _length++); + return _queue.skip(0).toString(); } /// Find the index of an object in the heap. @@ -343,7 +374,7 @@ /// A matching object, `o`, must satisfy that /// `comparison(o, object) == 0 && o == object`. int _locate(E object) { - if (_length == 0) return -1; + if (_queue.isEmpty) return -1; // Count positions from one instead of zero. This gives the numbers // some nice properties. For example, all right children are odd, // their left sibling is even, and the parent is found by shifting @@ -355,14 +386,14 @@ // in the heap will also have lower priority. do { var index = position - 1; - var element = _elementAt(index); + var element = _queue[index]; var comp = comparison(element, object); if (comp <= 0) { if (comp == 0 && element == object) return index; // Element may be in subtree. // Continue with the left child, if it is there. var leftChildPosition = position * 2; - if (leftChildPosition <= _length) { + if (leftChildPosition <= _queue.length) { position = leftChildPosition; continue; } @@ -375,19 +406,12 @@ } // Then go to the right sibling of the left-child. position += 1; - } while (position > _length); // Happens if last element is a left child. + } while ( + position > _queue.length); // Happens if last element is a left child. } while (position != 1); // At root again. Happens for right-most element. return -1; } - E _removeLast() { - var newLength = _length - 1; - var last = _elementAt(newLength); - _queue[newLength] = null; - _length = newLength; - return last; - } - /// Place [element] in heap at [index] or above. /// /// Put element into the empty cell at `index`. @@ -396,7 +420,7 @@ void _bubbleUp(E element, int index) { while (index > 0) { var parentIndex = (index - 1) ~/ 2; - var parent = _elementAt(parentIndex); + var parent = _queue[parentIndex]; if (comparison(element, parent) > 0) break; _queue[index] = parent; index = parentIndex; @@ -411,10 +435,10 @@ /// swap it with the highest priority child. void _bubbleDown(E element, int index) { var rightChildIndex = index * 2 + 2; - while (rightChildIndex < _length) { + while (rightChildIndex < _queue.length) { var leftChildIndex = rightChildIndex - 1; - var leftChild = _elementAt(leftChildIndex); - var rightChild = _elementAt(rightChildIndex); + var leftChild = _queue[leftChildIndex]; + var rightChild = _queue[rightChildIndex]; var comp = comparison(leftChild, rightChild); int minChildIndex; E minChild; @@ -435,8 +459,8 @@ rightChildIndex = index * 2 + 2; } var leftChildIndex = rightChildIndex - 1; - if (leftChildIndex < _length) { - var child = _elementAt(leftChildIndex); + if (leftChildIndex < _queue.length) { + var child = _queue[leftChildIndex]; var comp = comparison(element, child); if (comp > 0) { _queue[index] = child; @@ -445,17 +469,6 @@ } _queue[index] = element; } - - /// Grows the capacity of the list holding the heap. - /// - /// Called when the list is full. - void _grow() { - var newCapacity = _queue.length * 2 + 1; - if (newCapacity < _initialCapacity) newCapacity = _initialCapacity; - var newQueue = List<E?>.filled(newCapacity, null); - newQueue.setRange(0, _length, _queue); - _queue = newQueue; - } } /// Implementation of [HeapPriorityQueue.unorderedElements].
diff --git a/pkgs/collection/test/priority_queue_test.dart b/pkgs/collection/test/priority_queue_test.dart index f07a1a3..a7aafc4 100644 --- a/pkgs/collection/test/priority_queue_test.dart +++ b/pkgs/collection/test/priority_queue_test.dart
@@ -23,6 +23,35 @@ }); testInt(PriorityQueue<int>.new); testCustom(PriorityQueue<C>.new); + + group('(Heap)PriorityQueue.of returns functional priority queue', () { + List<int> extract(PriorityQueue<int> queue) { + var result = <int>[]; + while (queue.isNotEmpty) { + result.add(queue.removeFirst()); + } + return result; + } + + for (var i = 0; i < 1024; i = i * 2 + 1) { + test('size $i', () { + var input = List<int>.generate(i, (x) => x); + for (var j = 0; j < 5; j++) { + var copy = (input.toList()..shuffle()).where((_) => true); + { + var queue = HeapPriorityQueue<int>.of(copy, (a, b) => a - b); + var elements = extract(queue); + expect(elements, input); + } + { + var queue = HeapPriorityQueue<int>.of(copy, (a, b) => a - b); + var elements = extract(queue); + expect(elements, input); + } + } + }); + } + }); } void testInt(PriorityQueue<int> Function() create) { @@ -278,9 +307,9 @@ var q = HeapPriorityQueue<int>((a, b) => a - b) ..addAll([6, 4, 2, 3, 5, 8]); var e = q.unorderedElements; - q.add(12); // Modifiation before creating iterator is not a problem. + q.add(12); // Modification before creating iterator is not a problem. var it = e.iterator; - q.add(7); // Modification after creatig iterator is a problem. + q.add(7); // Modification after creating iterator is a problem. expect(it.moveNext, throwsConcurrentModificationError); it = e.iterator; // New iterator is not affected. @@ -294,9 +323,9 @@ var q = HeapPriorityQueue<int>((a, b) => a - b) ..addAll([6, 4, 2, 3, 5, 8]); var e = q.unorderedElements; - q.addAll([12]); // Modifiation before creating iterator is not a problem. + q.addAll([12]); // Modification before creating iterator is not a problem. var it = e.iterator; - q.addAll([7]); // Modification after creatig iterator is a problem. + q.addAll([7]); // Modification after creating iterator is a problem. expect(it.moveNext, throwsConcurrentModificationError); it = e.iterator; // New iterator is not affected. expect(it.moveNext(), true); @@ -311,10 +340,10 @@ ..addAll([6, 4, 2, 3, 5, 8]); var e = q.unorderedElements; expect(q.removeFirst(), - 2); // Modifiation before creating iterator is not a problem. + 2); // Modification before creating iterator is not a problem. var it = e.iterator; expect(q.removeFirst(), - 3); // Modification after creatig iterator is a problem. + 3); // Modification after creating iterator is a problem. expect(it.moveNext, throwsConcurrentModificationError); it = e.iterator; // New iterator is not affected.