查找Mathematica列表的第一个元素大于阈值

Question

我想知道如何获得大于给定阈值的(已经订购的)列表的第一个元素.

我不太了解Mathematica中的列表操作功能,也许有人可以给我一个高效的技巧.

Answer 1

Select 做你需要的,并且会保持一致,尊重列表的预先存在的顺序:

Select[list, # > threshold &, 1]

例如:

In[1]:= Select[{3, 5, 4, 1}, # > 3 &, 1]

Out[1]= {5}

您可以在第二个参数中提供所需的任何阈值或标准函数.

第三个参数指定只匹配一个(即第一个)元素.

希望有所帮助!

Answer 2

Joe正确地在他的回答中指出,人们会期望二进制搜索技术比Select这更快,即使列表已经排序,它似乎只是进行线性搜索:

ClearAll[selectTiming]
selectTiming[length_, iterations_] := Module[
    {lst},
    lst = Sort[RandomInteger[{0, 100}, length]];
    (Do[Select[lst, # == 2 &, 1], {i, 1, iterations}] // Timing // 
     First)/iterations
  ]

(为了演示目的,我任意将阈值设为2).

但是,BinarySearchCombinatorica中的函数是a)不合适(它返回的元素与请求的元素匹配,但不是第一个(最左边),这就是问题所在.

为了获得大于阈值的最左边元素,给定一个有序列表,我们可以递归地进行:

binSearch[lst_,threshold_]:= binSearchRec[lst,threshold,1,Length@lst]

(*
return position of leftmost element greater than threshold
breaks if the first element is greater than threshold
lst must be sorted
*)
binSearchRec[lst_,threshold_,min_,max_] :=
    Module[{i=Floor[(min+max)/2],element},
        element=lst[[i]];
        Which[
            min==max,max,
            element <= threshold,binSearchRec[lst,threshold,i+1,max],
            (element > threshold) && ( lst[[i-1]] <= threshold ), i,
            True, binSearchRec[lst,threshold,min,i-1]
        ]
    ]

或迭代地:

binSearchIterative[lst_,threshold_]:=Module[
    {min=1,max=Length@lst,i,element},
    While[
        min<=max,
        i=Floor[(min+max)/2];
        element=lst[[i]];
        Which[
            min==max, Break[],
            element<=threshold, min=i+1,
            (element>threshold) && (lst[[i-1]] <= threshold), Break[],
            True, max=i-1
        ]
    ];
    i
]

递归方法更清晰但我会坚持迭代方法.

为了测试它的速度,

ClearAll[binSearchTiming]
binSearchTiming[length_, iterations_] := Module[
    {lst},
    lst = Sort[RandomInteger[{0, 100}, length]];
    (Do[binSearchIterative[lst, 2], {i, 1, iterations}] // Timing // 
     First)/iterations
  ]

哪个产生

所以,更快,更好的缩放行为.

实际上没有必要编译它,但我还是做了.

总之,那么,不要Select用于长列表.

这就是我的答案.有关于手动或通过Combinatorica包进行二进制搜索的一些注释.

我比较了(编译)短常规的速度做二进制搜索VS的BinarySearch距离Combinatorica.请注意,这不做些什么的问题问什么(同样没有BinarySearch从Combinatorica); 我上面给出的代码.

二进制搜索可以迭代地实现为

binarySearch = Compile[{{arg, _Integer}, {list, _Integer, 1}},
           Module[ {min = 1, max = Length@list,
                 i, x},
               While[
                    min <= max,
                    i = Floor[(min + max)/2];
                    x = list[[i]];
                    Which[
                         x == arg, min = max = i; Break[],
                         x < arg, min = i + 1,
                         True, max = i - 1
                     ]
                ];
               If[ 0 == max,
                   0,
                   max
               ]
           ], 
        CompilationTarget -> "C", 
        RuntimeOptions -> "Speed"
];

我们现在可以比较这和BinarySearch从Combinatorica.注意,)名单必须进行排序b)本不会返回第一个匹配的元素,但一个匹配的元素.

lst = Sort[RandomInteger[{0, 100}, 1000000]];

让我们比较两个二进制搜索例程.重复50000次:

Needs["Combinatorica`"]
Do[binarySearch[2, lst], {i, 50000}] // Timing
Do[BinarySearch[lst, 2], {i, 50000}] // Timing
(*
{0.073437, Null}
{4.8354, Null}
*)

所以手写的更快.现在实际上二进制搜索只是访问列表中的6-7个点来获取这些参数(例如类似{500000, 250000, 125000, 62500, 31250, 15625, 23437}的东西),显然差异只是开销; BinarySearch例如,或许是更一般的,或者没有编译.

Answer 3

你可能也想看看TakeWhile []和LengthWhile [].

http://reference.wolfram.com/mathematica/ref/TakeWhile.html http://reference.wolfram.com/mathematica/ref/LengthWhile.html