8

我正在使用python。我有两个列表，列表 1 是 7000 个整数，列表 2 是 25000 个整数。我想遍历列表 1 中的每个数字，并找到列表 2 中比列表 1 中每个数字大的最接近的数字和最接近的小于列表 1 中每个数字的数字，然后计算列表 2 中这两个数字之间的差。到目前为止我有：

for i in list1:
    for j in list 2:
        if list2[j]<list1[i]:
            a = max(list2)
        elif list2[j]>list1[i]:
            b = min(list2)
            interval = b-a

这似乎不起作用。我想找到列表 2 中小于列表 1 中特定数字的显式数字并知道最大值，然后找出列表 2 中大于列表 1 中的数字的最小数字。有没有人有任何想法? 谢谢

4

4 回答 4

6

您可以使用bisect模块，最坏情况的复杂性O(N * logN)：

import bisect
lis1 = [4, 20, 26, 27, 30, 53, 57, 76, 89, 101]
lis2 = [17, 21, 40, 49, 53, 53, 53, 53, 70, 80, 81, 95, 99] #this must be sorted
#use lis2.sort() in case lis2 is not sorted
for x in lis1:
       #returns the index where x can be placed in lis2, keeping lis2 sorted
       ind=bisect.bisect(lis2,x) 
       if not (x >= lis2[-1] or x <= lis2[0]):
           sm, bi = lis2[ind-1], lis2[ind]

           if sm == x:  
               """ To handle the case when an item present in lis1 is 
               repeated multiple times in lis2, for eg 53 in this case"""
               ind -= 1
               while lis2[ind] == x:
                   ind -= 1
               sm = lis2[ind]

           print "{} <= {} <= {}".format(sm ,x, bi)

输出：

17 <= 20 <= 21
21 <= 26 <= 40
21 <= 27 <= 40
21 <= 30 <= 40
49 <= 53 <= 70
53 <= 57 <= 70
70 <= 76 <= 80
81 <= 89 <= 95

虽然这不会为4and输出任何内容101，因为 4 小于 lis2 中的任何元素，而 101 大于 lis2 中的任何元素。但如果需要，可以修复。

于 2013-05-28T12:14:01.777 回答
6

这是使用 NumPy 的矢量化解决方案。它应该非常快，因为它在 Python 中没有循环（除了最后的打印阶段）。

import numpy as np

# set up fake data
l1 = np.array([1.9, 2, 2.1]) # or whatever list you have
l2 = np.array([1, 2, 5, 10]) # as above
l2.sort() # remove this line if it's always sorted

# the actual algorithm
indexes = np.searchsorted(l2, l1, side='right')
lower = l2[indexes - 1]
upper = l2[indexes]
diffs = upper - lower

# print results for debugging
for value, diff in zip(l1, diffs):
    print "value", value, "gap", diff

这是上面硬编码测试数据的输出：

value 1.9 gap 1
value 2.0 gap 3
value 2.1 gap 3
于 2013-05-28T12:26:53.420 回答
3

首先，你的例子不是有效的代码，或者至少它没有做你想做的事。如果你有

for i in list1:

那么 i 不是索引，而是 list1 的一个元素。所以首先你会比较 i 和 j，而不是 list[i] 和 list[j]。

使用列表推导应该更容易>

for i in list1:
    a = max([n for n in list2 if n < i])
    b = min([n for n in list2 if n > i])

您可能必须添加一个 if 或两个来确保 a 和 b 存在，但它应该像这样工作。

于 2013-05-28T12:11:21.767 回答
0

这是一个不使用 numpy、bisect 模块或列表推导的解决方案！享受

list1=[1,2,4,8,16,32,64]
list2=[3,6,9,12,15,18,21]

correct={4:3, 8:3, 16:3}

lower=0
for t in list1:
  print t
  difference = 0
  index = lower
  while (difference == 0 and index<len(list2)-1):
    print "consider %d < %d and %d > %d" % (list2[index],t,list2[index+1],t)
    if list2[index]<t and list2[index+1] > t:
          lower = index
          upper = index + 1
          difference = list2[upper] - list2[lower]                              
          print "%d difference %d" % (t,list2[upper] - list2[lower])
          break
    index = index +1

  if t in correct.keys():
       assert(difference == correct[t])
于 2013-05-28T12:55:11.180 回答