Бинарный поиск без явного массива - PullRequest
Новая
       6

Бинарный поиск без явного массива

1 голос
/ 28 июня 2019

Я хочу выполнить бинарный поиск, например, с помощью np.searchsorted, однако, я не хочу создавать явный массив, содержащий значения. Вместо этого я хочу определить функцию, дающую ожидаемое значение в желаемой позиции массива, например, p(i) = i, где i обозначает позицию в массиве.

Создание массива значений, касающихся функции, в моем случае не будет ни эффективным, ни элегантным. Есть ли способ добиться этого?

Ответы [ 2 ]

2 голосов
/ 28 июня 2019

Как насчет чего-то вроде: 

import collections

class GeneratorSequence(collections.Sequence):
    def __init__(self, func, size):
        self._func = func
        self._len = size

    def __len__(self):
        return self._len

    def __getitem__(self, i):
        if 0 <= i < self._len:
            return self._func(i)
        else:
            raise IndexError

    def __iter__(self):
        for i in range(self._len):
            yield self[i]

Это будет работать с np.searchsorted(), например ::10000 * 

import numpy as np

gen_seq = GeneratorSequence(lambda x: x ** 2, 100)
np.searchsorted(gen_seq, 9)
# 3

Вы также можете написать свою собственную функцию бинарного поиска, вам не нужен NumPy в этом случае, и это может быть полезно: 

def bin_search(seq, item):
    first = 0
    last = len(seq) - 1
    found = False
    while first <= last and not found:
        midpoint = (first + last) // 2
        if seq[midpoint] == item:
            first = midpoint
            found = True
        else:
            if item < seq[midpoint]:
                last = midpoint - 1
            else:
                first = midpoint + 1
    return first

Что дает идентичные результаты: 

all(bin_search(gen_seq, i) == np.searchsorted(gen_seq, i) for i in range(100))
# True

Кстати, это также ПУТЬ быстрее: 

gen_seq = GeneratorSequence(lambda x: x ** 2, 1000000)

%timeit np.searchsorted(gen_seq, 10000)
# 1 loop, best of 3: 1.23 s per loop
%timeit bin_search(gen_seq, 10000)
# 100000 loops, best of 3: 16.1 µs per loop
1 голос
/ 28 июня 2019

Вдохновленный комментарием @ norok2, я думаю, вы можете использовать что-то вроде этого: 

def f(i):
    return i*2 # Just an example

class MySeq(Sequence):
    def __init__(self, f, maxi):
        self.maxi = maxi
        self.f = f
    def __getitem__(self, x):
        if x < 0 or x > self.maxi:
             raise IndexError()
        return self.f(x)
    def __len__(self):
        return self.maxi + 1

В этом случае f - ваша функция, а maxi - максимальный индекс. Это, конечно, работает, только если функция f возвращает значения в отсортированном порядке.
На данный момент вы можете использовать объект типа MySeq внутри np.searchsorted.

...