russell@unturf.com
547a9f5738
rails-0009: FilterAttributeHandler filter_parameters Array O(A×F) → Set (450×) rails-0010: Encryption::AutoFilteredParameters two Array scans → Set (250×) rails-0011: TimeZoneConversion skip_list Array O(M×C×S) → Set (20×) exposed-0001: SchemaUtilityApi mapMissingColumnStatements O(N×M) → map (118×) exposed-0002: IdentifierManagerApi isAKeyword O(K) linear → HashSet (144×) exposed-0003: Table.clone consParams.map fresh List → hoisted HashSet (6×) seaorm-0001: active_model establish_links leftover.any O(N²) → HashSet (501×) seaorm-0002: rbac engine group_permissions .values().find() → HashMap by ID (502×) seaorm-0003: schema builder sorted_tables Vec::contains → HashSet (500×) seaorm-0004: TopologicalSort from_iter seen Vec O(N²) → BTreeSet (28×) Unit tests: RailsTest 11/11, ExposedTest 3/3, SeaORMTest 4/4 PASS Whitepaper: 157→167 sites, 62→64 ecosystems; §13.12 ORM Wave 2 added
1 KiB
1 KiB
rails-0004: Enumerable#in_order_of — O(N log N × S) series.index in sort_by block
Severity: MEDIUM File: activesupport/lib/active_support/core_ext/enumerable.rb Line: ~45 (in_order_of method) Status: PATCHED
Description
Enumerable#in_order_of sorts a collection by the position of each element in a series
Array using sort_by { |e| series.index(e) }. Array#index is O(S) per call, and
sort_by invokes the block O(N log N) times — total O(N log N × S).
Used in ActiveRecord attribute ordering and result set sorting, so called on every query result set that uses custom ordering.
Root Cause
series.index(value) is an O(S) linear scan called inside a sort_by comparator block
that executes O(N log N) times. No position index is pre-built.
Fix
# BEFORE
sort_by { |element| series.index(element) || series.length }
# AFTER
series_map = series.each_with_index.to_h
sort_by { |element| series_map.fetch(element, series.length) }
Speedup
~10x at N=3000 collection, S=300 series