Подходящая структура данных для расчета прогрессивного налога

Question

Компания А имеет свою собственную систему, которую она использует для взимания налогов с продавцов. Налоги рассчитываются в прогрессивном порядке. Например, если продавец продает товар на сумму 25 долларов, то для первых 10 долларов налог = 8%, а для оставшихся 15 долларов налог = 7% Таким образом, общий налог = 8% от 25 + 7% от 15.

Таблица, которую они используют для расчета налога, выглядит следующим образом

$0 - $10 8%
$11 - $50 7%
$51 - $500 6%
$501 - $10000 5%
$10001 -$1000000 4% and so on.

Какую структуру данных вы бы использовали для хранения этой таблицы и как бы вы использовали эту структуру данных для кодирования функции float computeTaxableAmount(float amount) {}

Answer 1

Я бы использовал массив структур. Рассмотрим:

fields: from  to    percentage cumulative

values: 0     10    0.08       0
        10    50    0.07       0.80 (= (to-from)*percentage from row above)
        50    500   0.06       0.80 + (50-10)*0.07 = 4.00
        500   10000 0.05       4.00 + (500-50)*0.06 = 31.00
        ...

Обратите внимание на кумулятивное поле: промежуточная сумма комбинированного налога, подразумеваемая простым достижением данной налоговой категории. Затем, скажем, вы хотите, чтобы налог на некоторые продажи составлял X долларов, вы найдете строку, содержащую X (то есть from <= X < to), и общий налог будет:

(X - from) * percentage + cumulative

Предварительный расчет комбинированного налога из предыдущих налоговых скобок экономит бессмысленное повторение математики во время выполнения программы.

Вы можете выполнить бинарный поиск, чтобы обнаружить, что единая налоговая скобка X попадает в список, но - поскольку элементов так мало - накладные расходы на расчет / перемещение зондирующих позиций могут стоить больше, чем «промахи» от линейного поиска. (Если вы в отчаянии или скучаете, есть некоторые нанооптимизации, которые вы могли бы изучить, например, начиная со средней строки, чтобы минимизировать пропуски в худшем случае, или начиная со строки, которую вы последний раз сопоставляли, если входные значения имеют тенденцию быть похожими и т. Д.) *