Поскольку вы уже знаете, какое из 2 ^ 24 значений вам нужно сохранить (т. Е. 2 ^ 7 значений, которые вы определили как важные), мы можем просто отфильтровать входящие данные и присвоить значение, начиная с 0 и выше2 ^ 7-1, к этим значениям, как мы с ними сталкиваемся.Конечно, нам понадобится какой-то способ отследить, какое из важных значений мы уже видели и уже присвоили метку в [0,2 ^ 7).Для этого мы можем использовать некоторую реализацию словаря на основе дерева или хеш-таблицы (например, std::map в C ++, HashMap или TreeMap в Java или dict в Python).
Код может выглядетьчто-то вроде этого (я использую гораздо меньший диапазон значений):
import random
def make_mapping(data, important):
mapping=dict() # dictionary to hold the final mapping
next_index=0 # the next free label that can be assigned to an incoming value
for elem in data:
if elem in important: #check that the element is important
if elem not in mapping: # check that this element hasn't been assigned a label yet
mapping[elem]=next_index
next_index+=1 # this label is assigned, the next new important value will get the next label
return mapping
if __name__=='__main__':
important_values=[1,5,200000,6,24,33]
data=range(0,300000)
random.shuffle(data)
answer=make_mapping(data,important_values)
print answer
Вы можете значительно ускорить поиск, используя структуру данных на основе хеш / дерева для набора важных значений.Это сделало бы всю процедуру O(n*log(k)) (или O(n), если она является хеш-таблицей), где n - это размер входных данных, а k - множество важных значений.