Таблица поиска на уровне Python

Question

Я пытаюсь создать структуру данных, похожую на словарь в Python, но с ключами ранжирования. Вот сценарий:

Я реализую язык программирования для обратной совместимости со старой игрой. Каждая инструкция в игре помещается в список, и при каждом столкновении с символом новой строки увеличивается счетчик. Есть надежда, что если у языка будет ошибка во время выполнения, он сможет посмотреть, на какой строке была указана инструкция в таблице, и отобразить ее обратно пользователю.

Итак, если ошибка произошла в инструкции 20, а строка 3 содержала инструкции 15-30, то при опросе этой структуры для 20 должно возвращаться 3.

Наличие словаря с записью для каждой отдельной инструкции возможно, но также очень расточительно. Есть ли другой способ сделать это?

Answer 1

Из вашего описания у вас есть монотонно увеличивающийся счетчик и функция карты вида (константы ниже только что составлены, например):

 0 <= x <  5: 0
 5 <= x <  7: 1
 7 <= x < 10: 2
10 <= x < 18: 3
18 <= x < 21: 4

Кажется, что достаточно простого массива (списка, в Python) точек перехода:

[5, 7, 10, 18, 21]

и затем при заданном x вы найдете наименьшее значение i, такое что arr [i]> = x.

Вы можете найти этот индекс с помощью интерполяционного поиска, который будет примерно равен O (log log n), где n - длина массива (код, оставленный в качестве упражнения :-)).

Answer 2

«Наличие словаря с записью для каждой отдельной инструкции возможно, но также очень расточительно». Ожидаете ли вы, что программы, написанные на этом языке, будут содержать миллионы инструкций? Если нет, то это именно то, что я бы порекомендовал. Не оптимизируйте преждевременно. Большинство людей интерпретируют эту пословицу как относящуюся к производительности, но это относится и к использованию ресурсов.

Если вам нужно оптимизировать пространство, я бы порекомендовал, если вы используете Python 2.6 или новее, это bytearray. Как следует из его названия, это массив байтов, и поэтому он может представлять значения 0-255. Каждый элемент в массиве будет представлять количество операторов в соответствующей строке. Преобразовать из номера инструкции обратно в номер строки будет что-то вроде этого:

instcounts = bytearray((2, 4, 6, 3, 1, 1, 5, 2, 3))

def getline(instnumber):
    count = line = 0
    while count <= instnumber and line < len(instcounts):
        count += instcounts[line]
        line += 1
    return line  # conveniently, this will be 1-indexed  :-)

getline(15)    # tells me instruction 15 is on line 5

Преимущество этого ответа перед ответом torek заключается в том, что он хранит практически одинаковую информацию только в одном байте на строку исходного кода: намного более эффективно, чем список. Вам нужно проделать небольшую дополнительную работу, чтобы выяснить номер строки, но на практике вы никогда не заметите даже очень большие файлы, и вы будете запускать его только при печати сообщений об ошибках, что вряд ли является критичной для скорости функцией. Приведенная выше функция занимает около одной десятой секунды на bytearray, представляющем 1 000 000 строк, и это неоптимизированный код в Python 3.1 на виртуальной машине Windows XP, работающей на 4-летнем Mac Pro.

Требуется память? 1 087 199 байт, примерно четверть того, что требуется для только для списка в решении torek - не считая int объектов, на которые есть ссылки в списке, каждый из которых составляет 14 байтов (CPython повторно использует пул однако для небольших целочисленных объектов небольшие файлы могут не использовать много, если для целых чисел будет использоваться дополнительная память.

Кстати, CPython использует очень похожую схему (см. func_code.co_lnotab или __code__.co_lnotab по любой функции).

Answer 3

Вот класс, который настраивает клавиши dict:

class rdict(dict):

    def __init__(self, incSize, *args):
        self.incSize = incSize
        dict.__init__(self, *args)

    def __normRange(self, keyArg, incSize):
        return keyArg // incSize * incSize

    def __getitem__(self, key):
            return dict.__getitem__(self, self.__normRange(key, self.incSize))

        def __setitem__(self, key, value):
            dict.__setitem__(self, self.__normRange(key, self.incSize), value)

    g = input("hi")
    d = rdict(3)
    d[10.4] = "a"
    print d

Он выводит: {9.0: "a"}

Если вы не собираетесь его много использовать, забудьте окласс и просто введите ваши данные через функцию normRange