Таблицы поиска для повышения эффективности программирования

В этой статье мы рассмотрим, как можно улучшить программы, используя табличный поиск, а не длинные серии операторов if-else if. Разберем три примера на PHP, Python и JavaScript.

Решение с операторами if-else if

Давайте начнем с проблемы даты. Предположим, вам необходимо сопоставить месяц с количеством дней в этом месяце. Первое, что приходит в голову - это использовать много if-else if, которое присваивает дни определенному месяцу. Вот как это выглядит на PHP:

$month = 3;

if ($month == 1)
  $days = 31;
elseif ($month == 2)
  $days = 28;
elseif ($month == 3)
  $days = 31;
elseif ($month == 4)
  $days = 30;
elseif ($month == 5)
  $days = 31;
elseif ($month == 6)
  $days = 30;
elseif ($month == 7)
  $days = 31;
elseif ($month == 8)
  $days = 31;
elseif ($month == 9)
  $days = 30;
elseif ($month == 10)
  $days = 31;
elseif ($month == 11)
  $days = 30;
elseif ($month == 12)
  $days = 31;

echo $days;

Это очень длинная серия операторов.

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

Вот инструкция по созданию этого списка:

$monthDays = [0,31,28,31,30,31,30,31,31,30,31,30,31];

Обратите внимание, что у нас есть 0 в первом элементе списка, так как мы не нумеруем месяцы, начинающиеся с 0. Другой способ сделать это - начать с январских дней, а затем вычесть 1 из числа, которое пользователь вводит за месяц.

Вот полная программа:

$monthDays = [0,31,28,31,30,31,30,31,31,30,31,30,31];
$month = 3;
$days = $monthDays[$month];
echo $days;

Мы сократили 26-строчную программу до четырех строк, сделав ее более читаемой и более эффективной.

Поскольку мы сделали это для дней в месяце, мы также можем сделать это для названий месяцев, чтобы наша программа могла ссылаться на месяц по его имени, а не только по его номеру. Вот модифицированная программа PHP, в которой есть список названий месяцев:

$monthDays = [0,31,28,31,30,31,30,31,31,30,31,30,31];
$monthNames = ["", "January", "February", "March", "April",
              "May", "June", "July", "August", "September",
              "October", "November", "December"];
$month = 3;
$days = $monthDays[$month];
$monthName = $monthNames[$month];

echo $days." in ".$monthName;

Давайте рассмотрим еще один способ решения этой проблемы в Python.

Проблема сопоставления месяца с числом дней в нем является идеальной проблемой для словаря, который представляет собой структуру данных, которая сопоставляет ключ со значением. В этом случае месяц является ключом, а количество дней в месяце-значением.

Вот словарное решение проблемы дней в месяце:

daysInMonth = {
  "January" : 31,
  "February" : 28,
  "March" : 31,
  "April" : 28,
  "May" : 31,
  "June" : 30,
  "July" : 31,
  "August" : 31,
  "September" : 30,
  "October" : 31,
  "November" : 30,
  "December" : 31}
month = input("What month is it? ")
days = daysInMonth[month]
print(month,"has",days,"days in it.")

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

Пример булевой функции

Булева функция (функция, возвращающая логическое значение) может содержать таблицу поиска и использоваться вместо оператора if-else if. Однако сначала давайте рассмотрим пример, который не использует таблицу поиска в JavaScript.

Задача состоит в том, чтобы подсчитать количество гласных в строке. У вас может возникнуть соблазн проверить каждый символ строки с помощью оператора if-else if, например:

let sentence = "now is the time for all good people";
let count = 0;
for (let i = 0; i < sentence.length; i++) {
  if (sentence[i] == 'a' || sentence[i] == 'e' ||
      sentence[i] == 'i' || sentence[i] == 'o' ||
      sentence[i] == 'u') {
    count++;
  }
}
console.log("There are " + count + " vowels in the string.");

Но способ лучше - это хранить гласные в массиве, который затем проверяется, есть ли в нем указанный символ. Вот один из способов написания программы с помощью булевой функции:

function isVowel(ch) {
  let vowels = ['a','e','i','o','u'];
  if (vowels.includes(ch)) {
    return true;
  }
  return false;
}
let sentence = "now is the time for all good people";
let count = 0;
for (let i = 0; i < sentence.length; i++) {
  if (isVowel(sentence[i])) {
    count++;
  }
}
console.log("There are " + count + " vowels in the string.");

Одно из преимуществ этой программы по сравнению с предыдущей программой, которая использует оператор if-else if, заключается в том, что я использовал встроенную функцию массива JavaScript, includes. Использование встроенной функции более эффективно, чем перебор массива для сравнения каждого элемента с заданным символом, что заставило бы меня использовать if-else if в определении функции.

Использование таблицы поиска ступеней лестницы

Другой тип таблицы поиска - это таблица поиска ступеней лестницы. Данный тип таблицы используется, когда проблема не может быть решена с помощью “аккуратных” индексов массива или списка.

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

Отсечки для оценок: 50 или ниже F; до 65,0 D; до 75,0 C; до 90,0 B; и до 100,0 A.

Вот программа:

let gradeRange = [50.0, 65.0, 75.0, 90.0, 100.0];
let grades = ["F", "D", "C", "B", "A"];
let maxGrade = grades.length - 1;
let studentScore = 68.7;
let gradeLevel = 0;
let studentGrade = "A";
while (studentGrade == "A" && gradeLevel < maxGrade) {
  if (studentScore < gradeRange[gradeLevel]) {
    studentGrade = grades[gradeLevel]
  }
  gradeLevel++;
}
console.log("A score of " + studentScore + " is a letter grade of " +
      studentGrade + ".");

Этот код работает путем циклического перебора диапазона оценок и сравнения числового балла студента с перечисленными верхними пределами в массиве gradeRange. Буквенная оценка определяется, когда оценка студента превышает верхнюю часть диапазона.

Попытка написать эту программу с использованием логики if-else if сделает код слишком сложным и может привести к логическим ошибкам. Еще одно преимущество использования этого типа таблиц, как и в предыдущих примерах, заключается в том, что использование таблицы поиска облегчает изменение диапазона, если это необходимо.

Преимущества таблиц поиска

Есть несколько преимуществ использования таблиц поиска по сравнению с логикой if-else if. Во-первых, код, использующий таблицы поиска, легче читать, особенно когда оператор if-else if длинный. Еще одно преимущество заключается в том, что таблицы поиска легче обновлять, если меняется логика. Попытка изменить сложное утверждение if-else if

Если вы обнаружите, что у вас возникли проблемы с логикой оператора if-else if, подумайте о том, чтобы изменить его на таблицу поиска.