From 89c90492cacf3ae7b359fe9127fc5c197545a762 Mon Sep 17 00:00:00 2001 From: Tor Brede Vekterli Date: Thu, 24 Oct 2019 09:05:08 +0000 Subject: Make multi value attribute inserts O(n) instead of O(n^2) Previous code had O(n^2) complexity for * Weighted set appends, removes and weight updates * Array element removes (in-place erasing) New code moves all weighted set operations to a temporary hash map from key to weight, building a value vector at the very end. For arrays it defers all removals to the very end, amortizing cost down to linear time by tracking element removal times and avoiding push_backs instead of performing explicit element erasures. This fixes #11069 --- searchcore/src/tests/proton/docsummary/docsummary.cpp | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-) (limited to 'searchcore') diff --git a/searchcore/src/tests/proton/docsummary/docsummary.cpp b/searchcore/src/tests/proton/docsummary/docsummary.cpp index 0e521e473ae..26abd6be914 100644 --- a/searchcore/src/tests/proton/docsummary/docsummary.cpp +++ b/searchcore/src/tests/proton/docsummary/docsummary.cpp @@ -765,12 +765,14 @@ Test::requireThatAttributesAreUsed() EXPECT_EQUAL(2u, rep->docsums.size()); + // FIXME the expected output ordering of weighted set fields is currently inherently linked + // to the internal ordering of such attributes. Should be decoupled, as this is very fragile. EXPECT_TRUE(assertSlime("{ba:10,bb:10.1," "bc:'foo'," "bd:[20,30]," "be:[20.2,30.3]," "bf:['bar','baz']," - "bg:[{item:40,weight:2},{item:50,weight:3}]," + "bg:[{item:50,weight:3},{item:40,weight:2}]," "bh:[{item:40.4,weight:4},{item:50.5,weight:5}]," "bi:[{item:'quux',weight:7},{item:'qux',weight:6}]," "bj:'0x01020178017901016601674008000000000000'}", *rep, 0, true)); -- cgit v1.2.3