Таблица поиска - История изменений

Patarakin: /* Примеры */

2023-02-14T17:51:40Z

Примеры

← Предыдущая версия		Версия от 20:51, 14 февраля 2023
Строка 39:		Строка 39:

	== Примеры ==		== Примеры ==
	Пример таблицы синусов (на [[Си ~~(язык программирования)\|языке программирования{{nbsp}}C~~]]):		Пример таблицы синусов (на [[Си]]
	<source lang=c>		<source lang=c>
	// 8-битная таблица синусов		// 8-битная таблица синусов

Patarakin в 17:51, 14 февраля 2023

2023-02-14T17:51:02Z

← Предыдущая версия		Версия от 20:51, 14 февраля 2023
Строка 1:		Строка 1:
	'''Таблица поиска''' ~~({{lang-en\|lookup table}}) —~~ это [[структура данных]], в которой хранятся результаты [[Интерполяция\|интерполяции]] функции. Обычно это [[Массив (программирование)\|массив]] или [[ассоциативный массив]], используемый с целью заменить вычисления на операцию простого [[поиск]]а. Увеличение скорости может быть значительным, так как получить данные из памяти зачастую быстрее, чем выполнить трудоёмкие вычисления.		'''Таблица поиска''' — это [[структура данных]], в которой хранятся результаты [[Интерполяция\|интерполяции]] функции. Обычно это [[Массив (программирование)\|массив]] или [[ассоциативный массив]], используемый с целью заменить вычисления на операцию простого [[поиск]]а. Увеличение скорости может быть значительным, так как получить данные из памяти зачастую быстрее, чем выполнить трудоёмкие вычисления.

	Классический пример использования таблиц поиска — вычисление значений [[тригонометрические функции\|тригонометрических функций]], например, [[синус]]а. Его непосредственное вычисление может сильно замедлить работу приложения. Чтобы этого избежать, приложение при первом запуске заранее рассчитывает определённое количество значений синуса, например, для всех целых градусов. Потом, когда программе понадобится значение синуса, она использует таблицу поиска, чтобы получить приблизительное значение синуса из памяти, вместо того чтобы вычислять его значение (например, с помощью [[Числовой ряд\|рядов]]). Таблицы поиска также используются в математических [[сопроцессор]]ах; ошибка в таблице поиска в процессорах [[Pentium]] фирмы [[Intel]] привела к печально известной [[Ошибка Pentium FDIV\|ошибке]], уменьшавшей точность операции деления.		Классический пример использования таблиц поиска — вычисление значений [[тригонометрические функции\|тригонометрических функций]], например, [[синус]]а. Его непосредственное вычисление может сильно замедлить работу приложения. Чтобы этого избежать, приложение при первом запуске заранее рассчитывает определённое количество значений синуса, например, для всех целых градусов. Потом, когда программе понадобится значение синуса, она использует таблицу поиска, чтобы получить приблизительное значение синуса из памяти, вместо того чтобы вычислять его значение (например, с помощью [[Числовой ряд\|рядов]]). Таблицы поиска также используются в математических [[сопроцессор]]ах; ошибка в таблице поиска в процессорах [[Pentium]] фирмы [[Intel]] привела к печально известной [[Ошибка Pentium FDIV\|ошибке]], уменьшавшей точность операции деления.
Строка 7:		Строка 7:
	Существует промежуточное решение, когда используют таблицу поиска в сочетании с простыми вычислениями — [[интерполяция\|интерполяцией]]. Это позволяет более точно находить значения между двумя вычисленными заранее точками. Затраты времени немного возрастут, но взамен будет обеспечена бо́льшая точность вычислений. Также эту технику можно применять для уменьшения размеров таблицы поиска без потерь точности.		Существует промежуточное решение, когда используют таблицу поиска в сочетании с простыми вычислениями — [[интерполяция\|интерполяцией]]. Это позволяет более точно находить значения между двумя вычисленными заранее точками. Затраты времени немного возрастут, но взамен будет обеспечена бо́льшая точность вычислений. Также эту технику можно применять для уменьшения размеров таблицы поиска без потерь точности.

	Таблицы поиска широко используются также в компьютерной обработке изображений (в этой области соответствующие таблицы обычно называют «палитрами»). <!-- далее идёт специфика обработки изображений, которую я не очень понимаю. Воздержусь от перевода. The term transfer function is commonly used in literature to describe a color mapping used to highlight a range of values of interest. Windowing in computed tomography refers to a related concept. -->		Важно отметить, что использование таблиц поиска в тех задачах, в которых они неэффективны, приводит к понижению скорости работы. В некоторых языках программирования (например, в [[Java]]) обращение к таблице поиска может быть даже более «дорогим» из-за обязательной проверки границ, включающей в себя дополнительные сравнения и ветвления для каждой операции поиска.

	Важно отметить, что использование таблиц поиска в тех задачах, в которых они неэффективны, приводит к понижению скорости работы. Это происходит не только потому, что извлечение из памяти данных оказывается медленнее, чем их вычисление, но и потому, что таблица поиска может занять всю [[Оперативная память\|память]] и переполнить [[кэш]]. Если таблица велика, каждое обращение к ней, скорее всего, будет приводить к [[Кэш процессора#Принцип работы\|промаху кэша]]. В некоторых языках программирования (например, в [[Java]]) обращение к таблице поиска может быть даже более «дорогим» из-за обязательной проверки границ, включающей в себя дополнительные сравнения и ветвления для каждой операции поиска.

	Есть два фундаментальных ограничения на создание таблиц поиска. Первое — это общее количество доступной памяти: таблица должна умещаться в имеющийся объём, хотя можно сделать таблицу поиска и на диске, увеличив тем самым время операции поиска. Другое ограничение — это время, необходимое для создания таблицы поиска при первом запуске — хотя обычно эта операция нужна только один раз, она может отнимать слишком много времени, что делает использование таблиц поиска неподходящим решением.		Есть два фундаментальных ограничения на создание таблиц поиска. Первое — это общее количество доступной памяти: таблица должна умещаться в имеющийся объём, хотя можно сделать таблицу поиска и на диске, увеличив тем самым время операции поиска. Другое ограничение — это время, необходимое для создания таблицы поиска при первом запуске — хотя обычно эта операция нужна только один раз, она может отнимать слишком много времени, что делает использование таблиц поиска неподходящим решением.
Строка 27:		Строка 25:
	'''return''' sine_table[round(1000 * x / pi)]		'''return''' sine_table[round(1000 * x / pi)]

	~~[[Файл:Interpolation example linear.svg\|thumb\|right\|Линейная интерполяция функции синуса на некотором диапазоне.]]~~

	Таблица требует много памяти — например, если используются числа с плавающей запятой двойной точности, то понадобится {{num\|16000\|байт}}. Можно использовать меньшее количество точек, но тогда точность упадёт. Хорошей практикой в таком случае является [[линейное приближение]].		Таблица требует много памяти — например, если используются числа с плавающей запятой двойной точности, то понадобится {{num\|16000\|байт}}. Можно использовать меньшее количество точек, но тогда точность упадёт. Хорошей практикой в таком случае является [[линейное приближение]].
Строка 67:		Строка 64:

	[[Категория:Структуры данных]]		[[Категория:Структуры данных]]
	~~[[Категория:Обработка изображений]]~~

Patarakin: 1 версия импортирована

2022-10-19T07:30:42Z

1 версия импортирована

← Предыдущая версия		Версия от 10:30, 19 октября 2022
(нет различий)

109.195.69.130: поправил окончание

2021-07-20T05:50:13Z

поправил окончание

Новая страница

'''Таблица поиска''' ({{lang-en|lookup table}}) — это [[структура данных]], в которой хранятся результаты [[Интерполяция|интерполяции]] функции. Обычно это [[Массив (программирование)|массив]] или [[ассоциативный массив]], используемый с целью заменить вычисления на операцию простого [[поиск]]а. Увеличение скорости может быть значительным, так как получить данные из памяти зачастую быстрее, чем выполнить трудоёмкие вычисления.

Классический пример использования таблиц поиска — вычисление значений [[тригонометрические функции|тригонометрических функций]], например, [[синус]]а. Его непосредственное вычисление может сильно замедлить работу приложения. Чтобы этого избежать, приложение при первом запуске заранее рассчитывает определённое количество значений синуса, например, для всех целых градусов. Потом, когда программе понадобится значение синуса, она использует таблицу поиска, чтобы получить приблизительное значение синуса из памяти, вместо того чтобы вычислять его значение (например, с помощью [[Числовой ряд|рядов]]). Таблицы поиска также используются в математических [[сопроцессор]]ах; ошибка в таблице поиска в процессорах [[Pentium]] фирмы [[Intel]] привела к печально известной [[Ошибка Pentium FDIV|ошибке]], уменьшавшей точность операции деления.

Задолго до того, как таблицы поиска появились в программировании, они уже использовались людьми для облегчения ручных вычислений. Особенно были распространены [[таблицы логарифмов]], а также тригонометрических и статистических функций.

Существует промежуточное решение, когда используют таблицу поиска в сочетании с простыми вычислениями — [[интерполяция|интерполяцией]]. Это позволяет более точно находить значения между двумя вычисленными заранее точками. Затраты времени немного возрастут, но взамен будет обеспечена бо́льшая точность вычислений. Также эту технику можно применять для уменьшения размеров таблицы поиска без потерь точности.

Таблицы поиска широко используются также в компьютерной обработке изображений (в этой области соответствующие таблицы обычно называют «палитрами»). 

Важно отметить, что использование таблиц поиска в тех задачах, в которых они неэффективны, приводит к понижению скорости работы. Это происходит не только потому, что извлечение из памяти данных оказывается медленнее, чем их вычисление, но и потому, что таблица поиска может занять всю [[Оперативная память|память]] и переполнить [[кэш]]. Если таблица велика, каждое обращение к ней, скорее всего, будет приводить к [[Кэш процессора#Принцип работы|промаху кэша]]. В некоторых языках программирования (например, в [[Java]]) обращение к таблице поиска может быть даже более «дорогим» из-за обязательной проверки границ, включающей в себя дополнительные сравнения и ветвления для каждой операции поиска.

Есть два фундаментальных ограничения на создание таблиц поиска. Первое — это общее количество доступной памяти: таблица должна умещаться в имеющийся объём, хотя можно сделать таблицу поиска и на диске, увеличив тем самым время операции поиска. Другое ограничение — это время, необходимое для создания таблицы поиска при первом запуске — хотя обычно эта операция нужна только один раз, она может отнимать слишком много времени, что делает использование таблиц поиска неподходящим решением.

== Вычисление синуса ==
Большинство компьютеров поддерживают только основные [[арифметические операции]] и не могут вычислить значение синуса напрямую.
Вместо этого для вычисления значения синуса с высокой степенью точности они используют метод [[CORDIC]] или [[ряд Тейлора]]:
: <math>\sin x = x - \frac{x^3}{6} + \frac{x^5}{120} - \frac{x^7}{5040}+\ldots</math>

Однако такое вычисление может занять много времени, особенно на медленном процессоре, и существует множество приложений, например, [[компьютерная графика]], которым необходимо вычислять значение тысяч синусов каждую секунду. Распространённое решение — заранее вычислить таблицу значений синуса, и затем нахождение синуса числа сведётся к выбору ближайшего к этому числу аргумента из таблицы (соответствующее значение функции будет близко к правильному значению, потому что синус — [[непрерывная функция|непрерывная]] и ограниченная функция). Например:

''real array'' sine_table[-1000..1000]
'''for''' x '''from''' -1000 '''to''' 1000
sine_table[x] := sine(pi * x / 1000)

'''function''' lookup_sine(x)
'''return''' sine_table[round(1000 * x / pi)]

[[Файл:Interpolation example linear.svg|thumb|right|Линейная интерполяция функции синуса на некотором диапазоне.]]

Таблица требует много памяти — например, если используются числа с плавающей запятой двойной точности, то понадобится {{num|16000|байт}}. Можно использовать меньшее количество точек, но тогда точность упадёт. Хорошей практикой в таком случае является [[линейное приближение]].

Вот пример линейной аппроксимации:

'''function''' lookup_sine(x)
x1 := floor(x*1000/pi)
y1 := sine_table[x1]
y2 := sine_table[x1+1]
'''return''' y1 + (y2-y1)*(x/1000/pi-x1)

При использовании интерполяции зачастую выгодно использовать неравномерное распределение данных: в тех местах, где функция ближе всего к прямой, брать мало точек для вычисления функции, если же кривизна функции велика — брать больше точек из этого диапазона, чтобы аппроксимация больше походила на реальную кривую (см. также [[Интерполяция]]).

== Примеры ==
Пример таблицы синусов (на [[Си (язык программирования)|языке программирования{{nbsp}}C]]):
<source lang=c>
// 8-битная таблица синусов
const unsigned char sinetable[256] = {
128,131,134,137,140,143,146,149,152,156,159,162,165,168,171,174,
176,179,182,185,188,191,193,196,199,201,204,206,209,211,213,216,
218,220,222,224,226,228,230,232,234,236,237,239,240,242,243,245,
246,247,248,249,250,251,252,252,253,254,254,255,255,255,255,255,
255,255,255,255,255,255,254,254,253,252,252,251,250,249,248,247,
246,245,243,242,240,239,237,236,234,232,230,228,226,224,222,220,
218,216,213,211,209,206,204,201,199,196,193,191,188,185,182,179,
176,174,171,168,165,162,159,156,152,149,146,143,140,137,134,131,
128,124,121,118,115,112,109,106,103,99, 96, 93, 90, 87, 84, 81,
79, 76, 73, 70, 67, 64, 62, 59, 56, 54, 51, 49, 46, 44, 42, 39,
37, 35, 33, 31, 29, 27, 25, 23, 21, 19, 18, 16, 15, 13, 12, 10,
9, 8, 7, 6, 5, 4, 3, 3, 2, 1, 1, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 1, 1, 2, 3, 3, 4, 5, 6, 7, 8,
9, 10, 12, 13, 15, 16, 18, 19, 21, 23, 25, 27, 29, 31, 33, 35,
37, 39, 42, 44, 46, 49, 51, 54, 56, 59, 62, 64, 67, 70, 73, 76,
79, 81, 84, 87, 90, 93, 96, 99, 103,106,109,112,115,118,121,124
};
</source>
При этом значения синуса из [-1;1] отражены в целочисленый диапазон от минимального 0 до максимального 255, нулю соответствует 128. В подавляющем большинстве CPU операции с целыми числами происходят значительно быстрее, чем с плавающей запятой.

[[Категория:Структуры данных]]
[[Категория:Обработка изображений]]