python - 在 map 函数中使用多个迭代器

Question

我有一个函数，它使用 for 循环在由字符组成的二维列表中查找字符的起始位置。

def findStartPos(char, arr):
    for y, sublist in enumerate(arr):
        pos = []
        if char in sublist:
            x = arr[y].index(char)
            pos.append(x)
            pos.append(y)
            return pos
    return -1

如何用地图功能翻译这个？如果可能的话。考虑到我正在迭代作为 arr[y] 的 y 和作为 arr[y][x] 的子列表。此外，如果有任何其他方式来优化代码会有所帮助。

我还没有尝试过任何事情，因为我不知道如何前进。

标签： pythonpython-3.x

Answer 1

我相信您正在寻找优化而不仅仅是字典的应用？

提问时间！有没有比线性搜索更快的算法来搜索数组中的字符？除非对数组进行排序，否则答案通常是否定的。因此，您必须检查查询的所有索引。没有更快的解决方案。将矩阵转换为集合列表也不会优化它，因为集合转换的列表具有 O(n) 时间复杂度。

同样，如果您有一个矩阵但有多个查询，您可以预处理矩阵并在遍历矩阵时为字典中的每个唯一元素存储每个元素的位置（索引），并且您只需执行一次所有查询只需预处理一次。

我的实现：

from collections import defaultdict #to make life easier
def preprocess(matrix):
  dic_to_store_index=defaultdict(list)
  for i in range(len(matrix)):
          for m in range(len(matrix[i])):
                    dic_to_store_index[matrix[i][m]].append((i,m)) #Storing tuples of indexes
                    
  return dic_to_store_index

def find(dic,char):
  return dic[char][0]

matrix=[[5,6,5,4,2,4,5],[2,2,2,2],[2,7,2,1]] #Your matrix here
dic=preprocess(matrix) #preprocess only once for  all queries
char=2 #lets find first occurance of  2 in this matrix
print(find(dic,char)) # 0{1) operation
char=7 #another query
print(find(dic,char)) #O(1) complexity and no need to traverse matrix

这样，您不必为每个查询遍历整个矩阵。