Implement generic version of set operations that operate on a range of sets.
Reported by
dyaros...@yandex-team.ru,
Feb 25 2017
|
|||
Issue descriptionSometimes there is a need to do a union/intersect operation on many sets. Usually it's done in not the most efficient manner (look at url_index_private_data.cc for example). It would be great to design a generic solution that could be used everywhere. One of the desirable features is to support some form of projection, so that set could be obtained through some function call.
,
Feb 27 2017
@a... Well, it's not easy to create a bug that's not based on crash or a defect in chromium. The only way I know is to use report bug for ChromeOs and then I can write arbitrary text. However, I'm still forced to check operating system.
,
Feb 28 2017
You might want to give more specifics on what was discussed already here and how you see this being solved.
,
Mar 1 2017
We have a number of cases where we union/intersect a range of sets. Standard library provides functions: std::set_union/std::set_intersection that do union/intersection for ordered containers. In this task I suggest to write similar functions that work on many sets. Since often we do not have sets directly but rather they are obtained as the result of some expression, some support for this should be provided. This functions have to be benchmarked - at some point I did union for many sets like std::set_union (I used std::priority_queue to select minimum on each step) - it was slower than putting everything in a vector and sorting it, Here is some rough sketch for intersect - https://godbolt.org/g/vgCVmr - if a person who does this task finds it useful. I think that this task is worth doing because implementing union/intersect well is not easy and we would have one place for it, where it can be done really good if necessary. I also think that it's ok not to have a very high quality implementation on the first try since we'll have one place to improve it and tests.
,
Mar 2 2018
This issue has been available for more than 365 days with no owner or cc list, so archiving this bug. Please re-open or file a new bug if this is still an issue. For more details visit https://www.chromium.org/issue-tracking/autotriage - Your friendly Sheriffbot |
|||
►
Sign in to add a comment |
|||
Comment 1 by a...@chromium.org
, Feb 27 2017Status: Untriaged (was: Unconfirmed)