测试数组中的无效值

原文链接: https://www.nv5geospatialsoftware.com/Learn/Blogs/Blog-Details/testing-arrays-for-invalid-values

16955 为文章评分:

未评分

测试数组中的无效值

匿名作者 2014年6月19日，星期四

最近我在编写一个函数时，需要验证传入的数组不包含负值。我迅速使用 IDL 的 WHERE() 函数写了一个测试，但随后开始思考这种方法的效率，以及是否存在更快和/或更节省内存的实现方式。经过一番思考，我提出了几种不同的测试实现方案，并对它们的时间差异感到有些惊讶。

以下是我整理的一些测试代码，用于测试我想到的不同实现。我使用 TIC/TOC 例程来测量多次迭代的时间。每次迭代都使用 RANDOMN() 生成一个新数组，以避免任何可能影响结果的数据缓存。我在 IF 测试中加入了一个变量增量，以确保它不会被优化掉。

pro test_find_negatives
  compile_opt idl2

  arraySize = 1000000
  iterations = 100

  fooWhere = 0
  fooMin = 0
  fooTotal = 0
  fooHasValue = 0

  print, 'where'
  TIC
  FOR i = 1, iterations DO BEGIN
    seed = i
    data = RANDOMN(seed, arraySize)
    w = WHERE(data LT 0, count)
    IF (count GT 0) THEN BEGIN
      ++fooWhere
    ENDIF
  ENDFOR
  TOC

  print, 'min'
  TIC
  FOR i = 1, iterations DO BEGIN
    seed = i
    data = RANDOMN(seed, arraySize)
    IF (MIN(data) LT 0) THEN BEGIN
      ++fooMin
    ENDIF
  ENDFOR
  TOC

  print, 'total'
  TIC
  FOR i = 1, iterations DO BEGIN
    seed = i
    data = RANDOMN(seed, arraySize)
    IF (TOTAL(data LT 0) GT 0) THEN BEGIN
      ++fooTotal
    ENDIF
  ENDFOR
  TOC

  print, 'hasValue'
  TIC
  FOR i = 1, iterations DO BEGIN
    seed = i
    data = RANDOMN(seed, arraySize)
    IF ((data LT 0).HasValue(1)) THEN BEGIN
      ++fooHasValue
    ENDIF
  ENDFOR
  TOC

  print, fooWhere, fooMin, fooTotal, fooHasValue
end

如您所见，我想出了四种实现方案。第一种是经典的 WHERE() 函数，它返回所有坏值的数组。我本可以对返回的数组调用 N_ELEMENTS()，但我使用了更高效的位置参数，该参数返回找到的元素数量。第二种实现使用 MIN()，然后直接将结果与 0 比较。这种方法对于其他类型的测试可能用途有限，但对于查找负数它是有效的。第三种实现使用 TOTAL() 对临时布尔值数组的内容进行求和。正如我们将从计时结果中看到的，这种方法开销稍大，因为它必须创建那个临时数组。细心的读者会注意到第四种实现并想知道它是什么。这是 IDL 8.3.1 中新功能的预览，我们现在可以在变量上使用静态方法。在这种情况下，HasValue() 方法正在测试临时布尔值数组，以查看其中是否有任何值为真。与 TOTAL() 方法相比，它有一个轻微的优化，因为该方法具有短路逻辑，一旦找到所需值就立即返回，而不像 TOTAL() 那样必须处理整个数组。

现在来看计时结果，如下表所示。我使用了许多不同的迭代次数和数组大小运行代码，以查看数组大小和其他系统差异（如内存管理器）如何影响结果。列是不同的数组大小，行是四种方法的不同迭代次数。时间以毫秒为单位列出，这可能比 TIC/TOC 能够精确测量的精度更高。


WHERE 迭代次数	100	1000	10000	100000	1000000
100	0	5	44	371	3340
1000	9	47	427	3780	35000
10000	90	466	4330	37800	335000

MIN 迭代次数
100	1	3	32	339	3070
1000	7	36	311	3510	30900
10000	79	344	3320	34800	306000

TOTAL 迭代次数
100	1	4	36	371	3210
1000	8	39	353	3740	33100
10000	83	387	3780	36300	321000

HasValue 迭代次数
100	51	5	36	375	3280
1000	10	41	360	3760	33300
10000	105	410	3760	37000	327000

乍一看，计时结果看起来相对接近，但检查 Profiler View 后，我们发现这些测试主要由 RANDOMN() 函数主导。因此，我添加了另一个仅调用 RANDOMN() 并进行计时的 FOR 循环，然后减去这些时间，得到了更有趣的结果，这些结果比较了真正的数组测试逻辑。您不能使用 Profiler View 来执行此操作，因为在像 TOTAL() 这样的情况下，临时布尔值数组的创建不会被分析器测量。


WHERE 迭代次数	100	1000	10000	100000	1000000
100	0	2	14	77	246
1000	3	13	126	493	4550
10000	17	136	1340	8070	31700

MIN 迭代次数
100	1	0	2	45	64
1000	1	2	10	224	443
10000	6	14	322	5040	2260

TOTAL 迭代次数
100	1	1	6	77	207
1000	2	5	52	447	2700
10000	10	57	785	6580	17200

HasValue 迭代次数
100	51	2	6	81	282
1000	4	7	59	467	2900
10000	32	80	766	7290	23200

这些数字有趣得多，显示了不同方法在性能上的巨大差异。我们可以看到，将迭代次数增加 10 倍并不总是使时间增加 10 倍，但对于小数组，我认为我们更多地受到其他系统负载和计时器精度的影响。随着迭代次数的增加，我们也更有可能出现进程内存碎片，并在数字中看到这种影响。这在 MIN() 的 10,000 次迭代结果中最为明显，100,000 个元素的数组比 1,000,000 个元素的数组花费的时间更长。我认为这肯定是内存管理器在尝试为所有迭代查找连续内存块时遇到困难的情况。

但此分析的重要部分是更定性的结果：MIN() 远优于其他所有方法。这很可能是因为它不必像 TOTAL() 或 HasValue() 那样与内存管理器打交道来创建临时输入数组，也不必像 WHERE() 那样处理动态调整大小的结果数组。随着数组大小的增加，性能提升更为明显，因为它避免了分配越来越大的数组。但是 MIN() 的通用性不如其他选项，因此，例如，如果您要检查数组中是否只有奇数，那么您将无法使用 MIN()。

TOTAL() 函数位居第二，但仅比 HasValue() 快一点点。这两种方法都必须创建临时输入数组，这需要分配时间。我认为 TOTAL() 更快，因为它是一个自由函数，而 HasValue 是一个类方法，因此在解引用类以获取要调用的方法的内存地址时存在少量开销。

WHERE() 函数是最慢的。它避免了创建临时输入数组，但由于事先不知道将有多少输出元素，它必须为每个找到的元素使用数组追加，这导致内存管理器为每个找到的元素执行新的分配，从而造成很大压力。当然，如果您想知道哪些元素是无效的，您必须使用 WHERE() 并付出时间和空间上的代价，但如果您只想知道是否存在任何坏元素，这不是最佳选择。

总而言之，对于单次调用这些测试中的任何一个，数字差异并不大，但它们很好地展示了在设计代码时应如何考虑时间和空间效率。

为什么 Hadoop 是个大事件免费遥感数据