有效的方式来排序符合条件

Question

我有一个numpy的数组的数组：

a = np.array(["dcba", "abc", "bca", "bcda", "tda", "a"]) 

现在我已经衡量定字符串的距离与给定的数组，例如一个量化的Levenshtein编辑距离函数，用于字符串ab ：

l_distv("ab", a) 

回报：

array([3, 1, 3, 4, 3, 1]) 

我想排序的ARR以某种方式使得编辑距离小于2的任何元素移动到第一位置，而其余的移动到它们后面而不改变它们的顺序。因此，结果将是：

array(["abc", "a", "dcba", "bca", "bcda", "tda"]) 

我已经做到了这一点，但它是很丑陋，我认为还有一个更有效的方式。

Answer 1

如果你想节省排序，只希望把在前面小于2的这样一个l_dist的元素我可以建议一个答案：

我认为你应该首先创建一个索引数组

indices = l_distv("ab", a) < 2 # you wanted to move evrything below 2 at the front 

这可以很容易地使用面膜指标，因此，例如

a[indices] #returns all elements where the l_dist returns smaller than 2 
a[~indices] #returns everything >= 2 

所以你也可以通过这两个结合重建sorted阵列。

res = np.concatenate((a[indices], a[~indices])) 

但它可能是我误解了问题，你不想保持初始排序（您examplaric结果似乎表明它），真正排序。

我不知道这是否真的有效，但它的工作原理。

Answer 2

添加的元素和编辑距离在字典

dictionary = dict(zip(a,array)) 

然后根据编辑距离排序的字典

sorted_dictionary = sorted(dictionary.items(), key=operator.itemgetter(1)) 

Answer 3

您可以使用zip和sorted来得到您的结果。

inputs = numpy.array(["dcba", "abc", "bca", "bcda", "tda", "a"]) 
distances = l_distv("ab", inputs) # numpy.array([3, 1, 3, 4, 3, 1]) 
results = zip(inputs, distances) # [("dcba", 3), ("abc", 1), ...] 

# Sort tuples by second value 
sorted_results = sorted(results, key=lambda x: x[1]) 

output = [x[0] for x in sorted_results] # get just the sorted inputs 
output = numpy.array(output) # use if you need a Numpy array and not a list 

Answer 4

假设这些距离值存储在阵列dists，这里的一种方法 -

sort_idx = dists.argsort() 
mask = dists < 2 
out = np.concatenate((a[sort_idx[mask[sort_idx]]],a[~mask])) 

样品运行 -

In [144]: a 
Out[144]: 
array(['dcba', 'abc', 'bca', 'bcda', 'tda', 'a'], 
     dtype='|S4') 

In [145]: dists 
Out[145]: array([3, 1, 3, 4, 3, 0]) # Different from listed sample to 
            # show how it handles sorting 

In [146]: sort_idx = dists.argsort() 

In [147]: mask = dists < 2 

In [148]: np.concatenate((a[sort_idx[mask[sort_idx]]],a[~mask])) 
Out[148]: 
array(['a', 'abc', 'dcba', 'bca', 'bcda', 'tda'], 
     dtype='|S4') 

---

上述方法连接两个索引的部分的a，这在运行时可能不是非常有效。因此，考虑到性能，您可以创建一个连续的索引数组，然后在one-go中索引a。因此，从以前的实施最后一行必须改变，像这样 -

out = a[np.concatenate((sort_idx[mask[sort_idx]],np.where(~mask)[0]))]