从值和阈值高效创建一系列集合

huangapple
go评论110阅读模式
英文:

Efficient creation of a sequence of sets from values and thresholds

问题

以下是您要求的翻译内容：

给定一个按升序排列的较短阈值序列和众多值（无序）。

期望的结果是一个包含一系列 set 的序列，第一个包含所有低于最低/第一个阈值的不同值；接下来的值不低于最低阈值，但低于第二个阈值（如果有的话）；以此类推，直到最后一个阈值；最后包含所有不低于最高阈值的值。

关于 dict 有类似的问题（对于 有帮助的 解决方案的指导也欢迎），建议如下：

  1. from itertools import pairwise
  3. def partition(values, thresholds):
  4.     """ 将值划分为一系列集合，这些集合在由阈值指定的右开区间中包含值。"""
  5.     return [ { v for v in values if v < thresholds[0] }
  6.        ] + [ { v for v in values if lo <= v < hi }
  7.                                 for lo, hi in tuple(pairwise(thresholds))
  8.        ] + [ { v for v in values if thresholds[-1] <= v } ]

这个代码会对 values 迭代 len(thresholds)+1 次。

如何高效地创建一个根据 阈值 对 values 进行划分的 set 序列？

我未能找到对 SciPy/NumPy 有帮助的东西。使用 numpy.digitize() 来索引一个 add() 成员的数组与非平凡值 和 阈值的 partition_Kelly3b() 在同一领域内。

英文:

Given a shortish sequence of thresholds ordered ascendantly and numerous values (unordered).

Wanted result is a sequence of sets, first one containing all distinct values below the lowest/first threshold; next values not below lowest threshold, but below 2nd threshold, if any; and so on 'til last threshold; finally all values not below highest threshold.

There are similar questions about dicts (pointers to helpful solutions there welcome, too),
suggestions amounting to

  1. from itertools import pairwise
  3. def partition(values, thresholds):
  4.     """ Partition values into a list of sets 
  5.         with values in right-open intervals specified by thresholds.
  6.     """
  7.     return [ { v for v in values if v < thresholds[0] }
  8.        ] + [ { v for v in values if lo <= v < hi }
  9.                                 for lo, hi in tuple(pairwise(thresholds))
  10.        ] + [ { v for v in values if thresholds[-1] <= v } ]

This "iterates" values len(thresholds)+1 times.

How to efficiently create a sequence of sets partitioning values according to thresholds?

I failed to find something helpful SciPy/NumPy.
Using numpy.digitize() to index an array of add() members was in the ball park of partition_Kelly3b() for non-trivial values and thresholds.

答案1

得分: 2

各种解决方案的测试结果：

  1. 10000个数和3个阈值：
  2.   0.83 ± 0.00毫秒 partition_Kelly4
  3.   0.83 ± 0.00毫秒 partition_Kelly4c
  4.   0.83 ± 0.01毫秒 partition_Kelly4a
  5.   1.42 ± 0.02毫秒 partition_Kelly3b
  6.   1.55 ± 0.02毫秒 partition_Kelly3
  7.   1.76 ± 0.02毫秒 partition_Kelly2
  8.   1.93 ± 0.00毫秒 partition_Kelly4b
  9.   2.04 ± 0.01毫秒 partition_Kelly
  10.   2.55 ± 0.03毫秒 partition_original
  12. 10000个数和10个阈值：
  13.   0.86 ± 0.01毫秒 partition_Kelly4a
  14.   0.87 ± 0.01毫秒 partition_Kelly4c
  15.   0.88 ± 0.02毫秒 partition_Kelly4
  16.   1.98 ± 0.03毫秒 partition_Kelly4b
  17.   2.03 ± 0.03毫秒 partition_Kelly3b
  18.   2.06 ± 0.05毫秒 partition_Kelly2
  19.   2.22 ± 0.05毫秒 partition_Kelly3
  20.   2.52 ± 0.02毫秒 partition_Kelly
  21.   6.19 ± 0.19毫秒 partition_original
  23. 10000个数和100个阈值：
  24.   0.94 ± 0.02毫秒 partition_Kelly4a
  25.   0.97 ± 0.02毫秒 partition_Kelly4
  26.   0.99 ± 0.02毫秒 partition_Kelly4c
  27.   2.05 ± 0.03毫秒 partition_Kelly4b
  28.   2.62 ± 0.17毫秒 partition_Kelly2
  29.   3.41 ± 0.05毫秒 partition_Kelly
  30.   3.58 ± 0.33毫秒 partition_Kelly3b
  31.   3.91 ± 0.25毫秒 partition_Kelly3
  32.  60.49 ± 10.98毫秒 partition_original
  34. 错误：
  35.   partition_dankal444
英文:

Test results of various solutions:

  1. 10000 values and 3 thresholds:
  2.   0.83 ± 0.00 ms  partition_Kelly4
  3.   0.83 ± 0.00 ms  partition_Kelly4c
  4.   0.83 ± 0.01 ms  partition_Kelly4a
  5.   1.42 ± 0.02 ms  partition_Kelly3b
  6.   1.55 ± 0.02 ms  partition_Kelly3
  7.   1.76 ± 0.02 ms  partition_Kelly2
  8.   1.93 ± 0.00 ms  partition_Kelly4b
  9.   2.04 ± 0.01 ms  partition_Kelly
  10.   2.55 ± 0.03 ms  partition_original
  12. 10000 values and 10 thresholds:
  13.   0.86 ± 0.01 ms  partition_Kelly4a
  14.   0.87 ± 0.01 ms  partition_Kelly4c
  15.   0.88 ± 0.02 ms  partition_Kelly4
  16.   1.98 ± 0.03 ms  partition_Kelly4b
  17.   2.03 ± 0.03 ms  partition_Kelly3b
  18.   2.06 ± 0.05 ms  partition_Kelly2
  19.   2.22 ± 0.05 ms  partition_Kelly3
  20.   2.52 ± 0.02 ms  partition_Kelly
  21.   6.19 ± 0.19 ms  partition_original
  23. 10000 values and 100 thresholds:
  24.   0.94 ± 0.02 ms  partition_Kelly4a
  25.   0.97 ± 0.02 ms  partition_Kelly4
  26.   0.99 ± 0.02 ms  partition_Kelly4c
  27.   2.05 ± 0.03 ms  partition_Kelly4b
  28.   2.62 ± 0.17 ms  partition_Kelly2
  29.   3.41 ± 0.05 ms  partition_Kelly
  30.   3.58 ± 0.33 ms  partition_Kelly3b
  31.   3.91 ± 0.25 ms  partition_Kelly3
  32.  60.49 ± 10.98 ms  partition_original
  34. Wrong:
  35.   partition_dankal444

Code (Attempt This Online!):

  1. from itertools import pairwise
  2. import random
  3. from bisect import bisect, bisect_left
  4. from time import perf_counter as time
  5. from statistics import mean, stdev
  8. def partition_original(values, thresholds):
  9.     """ Partition values into a list of sets 
  10.         with values in right-open intervals specified by thresholds.
  11.     """
  12.     return [ { v for v in values if v < thresholds[0] }
  13.        ] + [ { v for v in values if lo <= v < hi }
  14.                                 for lo, hi in tuple(pairwise(thresholds))
  15.        ] + [ { v for v in values if thresholds[-1] <= v } ]
  18. def partition_Kelly(values, thresholds):
  19.     res = [set() for _ in thresholds]
  20.     res.append(set())
  21.     for v in values:
  22.         i = bisect(thresholds, v)
  23.         res[i].add(v)
  24.     return res
  27. def partition_Kelly2(values, thresholds):
  28.     res = [set() for _ in thresholds]
  29.     res.append(set())
  30.     for v in set(values):
  31.         i = bisect(thresholds, v)
  32.         res[i].add(v)
  33.     return res
  36. def partition_Kelly3(values, thresholds):
  37.     def partition(values, thresholds):
  38.         if not thresholds:
  39.             return [set(values)]
  40.         i = len(thresholds) // 2
  41.         threshold = thresholds[i]
  42.         hi = []
  43.         lo = [x for x in values if x < threshold or hi.append(x)]
  44.         return partition(lo, thresholds[:i]) + partition(hi, thresholds[i+1:])
  45.     return partition(set(values), thresholds)
  48. def partition_Kelly3b(values, thresholds):
  49.     def partition(values, thresholds):
  50.         if not thresholds:
  51.             return [set(values)]
  52.         i = len(thresholds) // 2
  53.         threshold = thresholds[i]
  54.         hi = [].append
  55.         lo = [x for x in values if x < threshold or hi(x)]
  56.         return partition(lo, thresholds[:i]) + partition(hi.__self__, thresholds[i+1:])
  57.     return partition(set(values), thresholds)
  60. def partition_Kelly4(values, thresholds):
  61.     values = sorted(set(values))
  62.     res = []
  63.     i = 0
  64.     for threshold in thresholds:
  65.         j = bisect_left(values, threshold)
  66.         res.append(set(values[i:j]))
  67.         i = j
  68.     res.append(set(values[i:]))
  69.     return res
  72. def partition_Kelly4a(values, thresholds):
  73.     values = sorted(set(values))
  74.     res = []
  75.     i = 0
  76.     for threshold in thresholds:
  77.         j = bisect_left(values, threshold, i)
  78.         res.append(set(values[i:j]))
  79.         i = j
  80.     res.append(set(values[i:]))
  81.     return res
  84. def partition_Kelly4b(values, thresholds):
  85.     values = sorted(values)
  86.     res = []
  87.     i = 0
  88.     for threshold in thresholds:
  89.         j = bisect_left(values, threshold)
  90.         res.append(set(values[i:j]))
  91.         i = j
  92.     res.append(set(values[i:]))
  93.     return res
  96. def partition_Kelly4c(values, thresholds):
  97.     def partition(start, stop, thresholds):
  98.         if not thresholds:
  99.             return [set(values[start:stop])]
  100.         i = len(thresholds) // 2
  101.         threshold = thresholds[i]
  102.         j = bisect_left(values, threshold, start, stop)
  103.         return partition(start, j, thresholds[:i]) + partition(j, stop, thresholds[i+1:])
  104.     values = sorted(set(values))
  105.     return partition(0, len(values), thresholds)
  108. def partition_dankal444(values, thresholds):
  109.     import bisect
  110.     sets = [set() for _ in range(len(thresholds) + 1)]
  112.     for value in values:
  113.         set_idx = bisect.bisect_left(thresholds, value)
  114.         sets[set_idx].add(value)
  115.     return sets
  118. funcs = [partition_original, partition_Kelly, partition_Kelly2, partition_Kelly3, partition_Kelly3b, partition_Kelly4, partition_Kelly4a, partition_Kelly4b, partition_Kelly4c, partition_dankal444]
  119. wrong = set()
  121. def test(n, k, repeat):
  122.     print(n, 'values and', k, 'thresholds:')
  123.     t0 = time()
  125.     times = {f: [] for f in funcs}
  126.     def stats(f):
  127.         ts = [t * 1e3 for t in sorted(times[f])[:5]]
  128.         return f'{mean(ts):6.2f} ± {stdev(ts):4.2f} ms '
  130.     for _ in range(repeat):
  131.         values = random.choices(range(n), k=n)
  132.         thresholds = [int((i+.5)/k * n) for i in range(k)]
  133.         expect = none = object()
  134.         for f in funcs:
  135.             t = time()
  136.             result = f(values, thresholds)
  137.             times[f].append(time() - t)
  138.             if expect is none:
  139.                 expect = result
  140.             elif result != expect:
  141.                 wrong.add(f)
  142.         funcs[:] = [f for f in funcs if f not in wrong]
  144.     for f in sorted(funcs, key=stats):
  145.         print(stats(f), f.__name__)
  147.     print()#time() - t0)
  149. test(10**4, 3, 100)
  150. test(10**4, 10, 80)
  151. test(10**4, 10**2, 25)
  152. print('Wrong:')
  153. for f in wrong:
  154.     print(' ', f.__name__)

答案2

得分: -1

使用 bisect.bisect_left 函数（文档）

  1. import bisect
  2. sets = [set() for _ in range(len(thresholds) + 1)]
  4. for value in values:
  5.     set_idx = bisect.bisect_left(thresholds, value)
  6.     sets[set_idx].add(value)

请注意，对于某些值/阈值大小，可能会更慢。随着大小的增加，性能应该比 OP 方法更好（O(nlogn) 对比 O(n^2)）

英文:

Using bisect.bisect_left function (docs)

  1. import bisect
  2. sets = [set() for _ in range(len(thresholds) + 1)]
  3. for value in values:
  4. set_idx = bisect.bisect_left(thresholds, value)
  5. sets[set_idx].add(value)

Note it might be slower for some sizes of values/thresholds. Larger the sizes performance should get better compared to OP method (O(nlogn) vs O(n^2))

huangapple
  • 本文由 发表于 2023年5月14日 19:12:40
  • 转载请务必保留本文链接：https://go.coder-hub.com/76247167.html
  • numpy
  • performance
  • python
  • python-3.x
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定