如何使此功能更有效率？
How do I make this function more efficient?
我正在尝试创建一个小型数据库，其中包含人员列表、他们的姓名、ID 以及随着时间的推移他们的收入。使用此数据库，我想找到他们的收入中位数。
我为人们构想的class结构是这样的
class Person {
string name;
string ID;
vector<int> Incomes;
};
而整个数据库的 class 结构只是一个包含这些收入的向量。
class Database{
vector<Person> somepeople;
};
假设我创建了一个名为收入中值的函数，returns 是该数据库中所有人的收入中值。显而易见的方法是遍历每个人，然后遍历收入向量中的每个值以创建一个包含所有值的列表，然后从中找到中位数。但是，这需要 O(n*k) 时间。有没有办法在 O(nlogn) 或更短的时间内实现这一点，包括 C++ STL 提供的方法？
嗯，只有当有两个 Incomes向量时，你才能在O(logk)中找到它们合并的中位数。因为，二进制搜索 启用该方法。
但除此之外，我认为没有什么可以避免线性遍历的。
认为即使事先对向量进行了排序，即使那样我们也不知道它们的值如何相互比较，中间元素可以随机出现在第 2 个或第 88 个向量中。
您的任务非常有趣！我从头开始为您实现了两种解决方案的代码。第一个解决方案更短，仅使用 standard C++ library，第二个解决方案比标准库解决方案更长，更难，但 3x 快。
您可以跳过下面的整个描述文本，只需 运行 底部提供的 C++ 代码。
第一个解决方案实现 class StdMedianFinder 以查找能够执行 3 个操作的中位数：
Add(value, count) - 这允许一次添加不同用户的多个收入，收入由 value 表示，count 表示出现的次数所有用户的收入。您可以在任何时间点添加任何用户的收入，例如，如果您的数据库不时更新新用户。
Del(value, count) - 这允许删除用户的收入，例如，如果用户从数据库中删除。 value 和 count 的含义与 Add() 操作中的相同。
Median() - 这种方法 returns 所有当前收入的中位数，这正是您在问题中想要的。方法非常快，returns无论有多少收入都立即取值，因为主要的时间和计算消费者是Add()和Del()。
正如你在上面看到的，库允许增量地做所有事情，这意味着在不同的时间点，你可以通过添加或删除一些用户或他们的部分收入来更新你的数据库。增量为小更新提供了非常快的速度，这意味着如果您有 1000 笔收入，例如需要 100 micro-seconds 将它们添加到结构中，然后再 added/removed 10 笔收入，那么它们将只占用 1%初始时间 - 只有 1 micro-second，因为 10 incomes / 1000 incomes = 1%.
上面的 Class 仅使用 std::map and nothing else. As it is known std::map implements sorted (by keys) container using Red-Black 二叉搜索树。 Adding/removing 一个元素到我的 class 大约需要 adding/removing 个元素到 std::map 的时间加上迭代器的一次前进（++it; 或 --it;）。 std::map 对于 adding/removing 一个元素使用大约 O(Log(N)) 时间，其中 N 是容器中已有的元素数量。因此，我的 class 中 adding/removing N 个元素的总时间需要 O(N * Log(N)) 时间。
在您的问题中，您指出您需要非常快速的解决方案。我的两个解决方案都给了 O(N * Log(N)) 时间来增加 N 不同的收入。如果你有n个用户，每个用户的收入k，正如你在问题中所说，那么我的N = n * k，这意味着时间是O(n * k * Log(n * k))。但有个好消息——当只做第一次计算 Median 时，这是全职的，稍后调用 median 会立即给出结果，因为它经常发生在所有数据库中，以后会不时添加或删除新用户，如果你add/remove 一个拥有 k 收入的用户，那么您只需要很少的额外时间 O(k * Log(n * k)) 来更新我的 class 和 re-compute 中位数。添加单个用户时，重要 不是对所有用户（整个数据库）进行整re-computation，而是只更新class这个单个用户的收入。
对于更大的第二个解决方案，并且快 3x 倍，我从头开始实现 so-called B-Tree 标准 C++ 库中不存在，并使用这棵树我implmented BTreeMedianFinder class 具有与第一个 class StdMedianFinder.
完全相同的界面
重要说明 我下面的所有代码（尤其是 B-Tree）都没有经过很好的测试，不适合 copy-pasting 投入生产产品。您要么必须 copy-paste 将其用于教育项目，要么在生产中使用之前进行一些额外的深入测试。
B-Tree 的实现方式是，除了存储在叶节点中的 (Key, Value)（即收入和相同收入的计数）之外，它还在中间节点中存储了 [= 的最大值121=] 和 sub-tree 中的收入总数。这允许非常快速地执行两个操作 - 给定收入值它快速回答收入在所有收入的排序列表中的位置是什么，并且给定收入在排序列表中的期望位置它快速回答收入的价值是多少该位置（第二个操作用于查找中位数，因为中位数基本上是该位置的收入值等于所有元素数量的一半）。
以下代码有几个相当大的测试，用于检查三个 classes BTree、StdMedianFinder、BTreeMedianFinder 的正确性和速度。程序在所有测试和速度测量的控制台计时中显示。
如果你有 Boost.StackTrace library installed in your system it can be used to show stacktrace to make exceptions messages more informative. By default in my code this feature is disabled by define #define USE_BOOST_STACKTRACE 0, which you can change to 1 to enable. Also work of this feature was tested fully only on Windows, for Linux system some small fixups might be needed inside includes or defines. Program binary should be compiled with symbols information included, for this add option /Z7 in MSVC compiler and -g in GCC/CLang。只有这个第 3 方库可以用作选项，除此之外，我的代码中只使用了标准 C++ 库。
如果你进行调试构建，不要忘记定义 _DEBUG 宏，如果定义了这个宏，我会在所有 classes 代码中做很多额外的断言检查额外测试代码正确性并防止错误和崩溃。
下面的代码无需任何修改即可完全编译和运行。如果你 运行 它会执行所有测试和速度测量并在控制台中显示它们。也可以点击下方Try it online!link看直播运行 GodBolt Linux 服务器上的此代码。
源代码在这里。由于 post 大小的 StackOveflow 限制为 30000 个字符，因此在外部 PasteBin 服务中提供 source code shared。我的 post 代码似乎有 41000 个字符长！您也可以点击上面的 Try it online! link，它在 GodBolt 服务器上复制了相同的源代码。
输出：
'Test BTree' time 1.188 sec
'Test StdMedianFinder' time 0.532 sec
'Test BTreeMedianFinder' time 0.535 sec
'Std_Finder Add' time 1.426 sec
'BTree_Finder Add' time 0.577 sec
'Std_Tree Add' time 1.249 sec
'Std_Finder Median' time 0.001 sec
'BTree_Finder Median' time 0.321 sec
'Std_Finder Del' time 1.252 sec
'BTree_Finder Del' time 0.477 sec
'Std_Tree Del' time 1.117 sec
'Test MedianFinders Speed Total' time 6.907 sec
为什么不使用 std::nth_element？这是 O(n)
如果元素个数为奇数=>中间元素为中位数
如果元素个数是偶数 => 找到迭代器左中元素，然后右中元素 min() of 2nd half
中位数是 *leftMiddle + (*rightMiddle - *leftMiddle) / 2;
我正在尝试创建一个小型数据库，其中包含人员列表、他们的姓名、ID 以及随着时间的推移他们的收入。使用此数据库，我想找到他们的收入中位数。
我为人们构想的class结构是这样的
class Person {
string name;
string ID;
vector<int> Incomes;
};
而整个数据库的 class 结构只是一个包含这些收入的向量。
class Database{
vector<Person> somepeople;
};
假设我创建了一个名为收入中值的函数，returns 是该数据库中所有人的收入中值。显而易见的方法是遍历每个人，然后遍历收入向量中的每个值以创建一个包含所有值的列表，然后从中找到中位数。但是，这需要 O(n*k) 时间。有没有办法在 O(nlogn) 或更短的时间内实现这一点，包括 C++ STL 提供的方法？
嗯，只有当有两个 Incomes向量时，你才能在O(logk)中找到它们合并的中位数。因为，二进制搜索 启用该方法。
但除此之外，我认为没有什么可以避免线性遍历的。
认为即使事先对向量进行了排序，即使那样我们也不知道它们的值如何相互比较，中间元素可以随机出现在第 2 个或第 88 个向量中。
您的任务非常有趣！我从头开始为您实现了两种解决方案的代码。第一个解决方案更短，仅使用 standard C++ library，第二个解决方案比标准库解决方案更长，更难，但 3x 快。
您可以跳过下面的整个描述文本，只需 运行 底部提供的 C++ 代码。
第一个解决方案实现 class StdMedianFinder 以查找能够执行 3 个操作的中位数：
Add(value, count)- 这允许一次添加不同用户的多个收入，收入由value表示，count表示出现的次数所有用户的收入。您可以在任何时间点添加任何用户的收入，例如，如果您的数据库不时更新新用户。Del(value, count)- 这允许删除用户的收入，例如，如果用户从数据库中删除。 value 和 count 的含义与 Add() 操作中的相同。Median()- 这种方法 returns 所有当前收入的中位数，这正是您在问题中想要的。方法非常快，returns无论有多少收入都立即取值，因为主要的时间和计算消费者是Add()和Del()。
正如你在上面看到的，库允许增量地做所有事情，这意味着在不同的时间点，你可以通过添加或删除一些用户或他们的部分收入来更新你的数据库。增量为小更新提供了非常快的速度，这意味着如果您有 1000 笔收入，例如需要 100 micro-seconds 将它们添加到结构中，然后再 added/removed 10 笔收入，那么它们将只占用 1%初始时间 - 只有 1 micro-second，因为 10 incomes / 1000 incomes = 1%.
Class 仅使用 std::map and nothing else. As it is known std::map implements sorted (by keys) container using Red-Black 二叉搜索树。 Adding/removing 一个元素到我的 class 大约需要 adding/removing 个元素到 std::map 的时间加上迭代器的一次前进（++it; 或 --it;）。 std::map 对于 adding/removing 一个元素使用大约 O(Log(N)) 时间，其中 N 是容器中已有的元素数量。因此，我的 class 中 adding/removing N 个元素的总时间需要 O(N * Log(N)) 时间。
在您的问题中，您指出您需要非常快速的解决方案。我的两个解决方案都给了 O(N * Log(N)) 时间来增加 N 不同的收入。如果你有n个用户，每个用户的收入k，正如你在问题中所说，那么我的N = n * k，这意味着时间是O(n * k * Log(n * k))。但有个好消息——当只做第一次计算 Median 时，这是全职的，稍后调用 median 会立即给出结果，因为它经常发生在所有数据库中，以后会不时添加或删除新用户，如果你add/remove 一个拥有 k 收入的用户，那么您只需要很少的额外时间 O(k * Log(n * k)) 来更新我的 class 和 re-compute 中位数。添加单个用户时，重要 不是对所有用户（整个数据库）进行整re-computation，而是只更新class这个单个用户的收入。
对于更大的第二个解决方案，并且快 3x 倍，我从头开始实现 so-called B-Tree 标准 C++ 库中不存在，并使用这棵树我implmented BTreeMedianFinder class 具有与第一个 class StdMedianFinder.
重要说明 我下面的所有代码（尤其是 B-Tree）都没有经过很好的测试，不适合 copy-pasting 投入生产产品。您要么必须 copy-paste 将其用于教育项目，要么在生产中使用之前进行一些额外的深入测试。
B-Tree 的实现方式是，除了存储在叶节点中的 (Key, Value)（即收入和相同收入的计数）之外，它还在中间节点中存储了 [= 的最大值121=] 和 sub-tree 中的收入总数。这允许非常快速地执行两个操作 - 给定收入值它快速回答收入在所有收入的排序列表中的位置是什么，并且给定收入在排序列表中的期望位置它快速回答收入的价值是多少该位置（第二个操作用于查找中位数，因为中位数基本上是该位置的收入值等于所有元素数量的一半）。
以下代码有几个相当大的测试，用于检查三个 classes BTree、StdMedianFinder、BTreeMedianFinder 的正确性和速度。程序在所有测试和速度测量的控制台计时中显示。
如果你有 Boost.StackTrace library installed in your system it can be used to show stacktrace to make exceptions messages more informative. By default in my code this feature is disabled by define #define USE_BOOST_STACKTRACE 0, which you can change to 1 to enable. Also work of this feature was tested fully only on Windows, for Linux system some small fixups might be needed inside includes or defines. Program binary should be compiled with symbols information included, for this add option /Z7 in MSVC compiler and -g in GCC/CLang。只有这个第 3 方库可以用作选项，除此之外，我的代码中只使用了标准 C++ 库。
如果你进行调试构建，不要忘记定义 _DEBUG 宏，如果定义了这个宏，我会在所有 classes 代码中做很多额外的断言检查额外测试代码正确性并防止错误和崩溃。
下面的代码无需任何修改即可完全编译和运行。如果你 运行 它会执行所有测试和速度测量并在控制台中显示它们。也可以点击下方Try it online!link看直播运行 GodBolt Linux 服务器上的此代码。
源代码在这里。由于 post 大小的 StackOveflow 限制为 30000 个字符，因此在外部 PasteBin 服务中提供 source code shared。我的 post 代码似乎有 41000 个字符长！您也可以点击上面的 Try it online! link，它在 GodBolt 服务器上复制了相同的源代码。
输出：
'Test BTree' time 1.188 sec
'Test StdMedianFinder' time 0.532 sec
'Test BTreeMedianFinder' time 0.535 sec
'Std_Finder Add' time 1.426 sec
'BTree_Finder Add' time 0.577 sec
'Std_Tree Add' time 1.249 sec
'Std_Finder Median' time 0.001 sec
'BTree_Finder Median' time 0.321 sec
'Std_Finder Del' time 1.252 sec
'BTree_Finder Del' time 0.477 sec
'Std_Tree Del' time 1.117 sec
'Test MedianFinders Speed Total' time 6.907 sec
为什么不使用 std::nth_element？这是 O(n) 如果元素个数为奇数=>中间元素为中位数 如果元素个数是偶数 => 找到迭代器左中元素，然后右中元素 min() of 2nd half 中位数是 *leftMiddle + (*rightMiddle - *leftMiddle) / 2;