Предупреждающий знак
Лос-Анджелес известен своими сложными парковочными знаками :
Это тотемы правил и исключений, и исключения из исключений. Часто, когда мы кодируем, мы забываем урок, который очевиден в этих нелепых признаках: люди понимают простые, последовательные правила, но терпят неудачу в
особых случаях .
Тривиальный пример
Допустим, вам дан массив целых чисел, и вы хотите вычислить сумму соседей каждого элемента. Попытайся:
Рубин
xxxxxxxxxx
1
[1, 3, 4, 5, 0, 1, 8]
Прежде чем продолжить, подумайте, как бы вы решили это самостоятельно.
Простой подход может выглядеть так:
Рубин
x
1
input = [1, 3, 4, 5, 0, 1, 8]
2
result = input.map.with_index do |_, i|
4
if i == 0 # <-- LEFT ENDPOINT
5
input[i+1]
6
elsif i == input.size - 1 # <-- RIGHT ENDPOINT
7
input[i-1]
8
else
9
input[i-1] + input[i+1] # <-- GENERAL CASE
10
end
11
end.to_a
Обратите внимание, как мы относимся к конечным точкам как к особым случаям, усложняя простое правило «суммировать обоих соседей каждого элемента». Лучше всего сначала преобразовать входные данные, чтобы особые случаи исчезали, оставляя только общий случай. Давайте дополним ввод нулями, но зациклим исходные элементы:
Джава
xxxxxxxxxx
1
0 1 3 4 5 0 1 8 0
2
--- ---
3
| |
4
+-- 3 --+
У каждого предмета теперь есть и левый, и правый сосед. Особые случаи исчезли, и простой алгоритм просвечивает.
Рубин
xxxxxxxxxx
1
input = [1, 3, 4, 5, 0, 1, 8]
2
padded = [0] + input + [0]
3
result = (1...padded.size-1).map do |i|
5
padded[i-1] + padded[i+1]
6
end.to_a
Вам также могут понравиться:
Преимущества алгоритмов обучения .
Еще один простой пример
Вы начинаете в нижней части (шаг A) 4-х ступенчатой лестницы, обозначенной следующим образом:
Джава
xxxxxxxxxx
1
____
3
| D
4
____|
5
O | C
6
|< ____|
7
/ \ | B
8
____|
9
A
Вы делаете n шаги, оборачиваясь сверху и снизу. Где вы в конечном итоге?
Если вы сделали 4 шага, вы закончили бы на шаге C - 3 шага, чтобы достичь вершины, развернуться, 1 шаг вниз. Наивно, вы могли бы смоделировать эту ступеньку лестницы: итерацию от 1 к n, пинг-понг текущего индекса внутри массива.
Но это неэффективно для большой стоимости n. Большинство программистов замечают, что каждые 6 шагов вы возвращаетесь к шагу A, поэтому « n ответ» должен равняться « n % 6 ответу» (остаток от деления n на 6).
Они могут решить это так:
Рубин
xxxxxxxxxx
1
STEP_LABELS = 'ABCD'.chars
2
STAIRCASE_HEIGHT = STEP_LABELS.size - 1
3
def final_step(n)
5
n = n % (2 * STAIRCASE_HEIGHT)
6
index = if n <= STAIRCASE_HEIGHT
8
n # never turn around
9
else
10
2 * STAIRCASE_HEIGHT - n # reach top and turn around
11
end
12
STEP_LABELS[index]
14
end
Это решение быстрое, но все же содержит ненужный особый случай: достижение вершины и разворот. Вместо этого мы можем «завершить лестницу», рассматривая проблему следующим образом:
Джава
xxxxxxxxxx
1
____
2
| D |
3
____| |____
4
O | C C |
5
|< ____| |____
6
/ \ | B B | --> wrap
7
____| |____ around
8
A
и идти в одном направлении, навсегда. Особые случаи «сверху и снизу» исчезают. Еще раз, код проще:
Рубин
xxxxxxxxxx
1
STEP_LABELS = 'ABCD'.chars
2
CIRCULAR_LABELS = STEP_LABELS + (STEP_LABELS[1...-1]).reverse
3
def final_step(n)
5
n = n % CIRCULAR_LABELS.size
6
CIRCULAR_LABELS[n]
7
end
Этот пример является прототипом: и модульная арифметика, и завершение симметрии являются общими методами при исключении особых случаев.
Долой вечера!
Допустим, вам дан массив массивов, и вы хотите исключить массивы четного размера, разделив первый и второй элементы следующим образом:
Рубин
xxxxxxxxxx
1
# odd length, even, slice odd length,
2
# unchanged into two unchanged
3
# V V V
4
input = [ [1], [1, 2, 3, 4], [1, 2, 3] ]
5
desired_output = [ [1], [1], [2, 3, 4], [1, 2, 3] ]
Хороший первый инстинкт должен использовать map:
Рубин
xxxxxxxxxx
1
input = [ [1], [1, 2, 3, 4], [1, 2, 3] ]
2
input.map { |x| x.size.even? ? [[x.first], [x.drop(1)]] : x }
4
#=> [[1], [[1], [[2, 3, 4]]], [1, 2, 3]]
Но вложение неправильное: мы хотим, чтобы разбиение производило два элемента, а не массив, содержащий два элемента. Вы можете отказаться здесь и использовать reduce:
Рубин
xxxxxxxxxx
1
input = [ [1], [1, 2, 3, 4], [1, 2, 3] ]
2
result = input.reduce([]) do |m, x|
4
x.size.even? ? (m << [x.first] << x.drop(1)) : m << x
5
end
6
#=> [[1], [1], [2, 3, 4], [1, 2, 3]]
Это было бы позором, потому что концептуально map лучше подходит. Наша map попытка не удалась, потому что в особых случаях используются четные элементы, заключающие в себе только те, которые находятся в массиве. Вместо этого давайте также обернем нечетные элементы, а затем удалим обтекание из всех элементов:
Рубин
xxxxxxxxxx
1
input = [ [1], [1, 2, 3, 4], [1, 2, 3] ]
2
result = input.map do |x|
4
x.size.even? ? [[x.first], x.drop(1)] : [x]
5
end.flatten(1)
6
#=> [[1], [1], [2, 3, 4], [1, 2, 3]]
Этот трюк принимает разные формы. В конечном счете, избегать особых случаев - значит делать вещи идентичными. Если вы не можете сделать особый случай общим, посмотрите, сможете ли вы сделать общий случай особенным.
Пример из реального мира
В системе, над которой я работал, часы работы продавца сохранялись в базе данных как битовые массивы, и каждый день разбивался на 24 * 12 = 288 5-минутные интервалы. Здесь для простоты мы будем использовать 24 часовых интервала - это ничего не изменит.
Если бы магазин был открыт с понедельника с 8:00 до 13:00, а затем снова с 14:00 до 19:00, наш массив битов по понедельникам будет выглядеть так:
Джава
xxxxxxxxxx
1
12am 8am 1pm 7pm 11pm
2
v v v v v
3
0 0 0 0 0 0 0 0 1 1 1 1 1 0 1 1 1 1 1 0 0 0 0 0
Цель состоит в том, чтобы отобразить эти битовые массивы в удобной для человека форме на веб-странице, как это делает Yelp:
Так как 01 отмечает открытое время и 10 отмечает близкое время, вы можете попробовать решение, подобное этому, и думать, что вы сделали:
Рубин
xxxxxxxxxx
1
# NOTE: The utility methods `all_indexes(arr, subarr)`, which returns
2
# the indexes of all matches of subarr within arr, and `to_12h(hour)`,
3
# which converts 24 hour time to 12 hour time, are defined in the link
4
# below, and at the end of the article.
5
#
6
bits = '000000001111101111100000'.chars.map(&:to_i)
8
open_times = all_indexes(bits, [0, 1]).map(&:succ).map(&to_12h)
9
close_times = all_indexes(bits, [1, 0]).map(&:succ).map(&to_12h)
10
hours = open_times.zip(close_times)
11
puts hours.map{ |x| x.join(' - ') }.join("\n")
12
#
14
# Output:
15
#
16
# 8am - 1pm
17
# 2pm - 7pm
Но что, если купец - скажем, клуб - открывается в полночь? 01 Будет отсутствовать. Аналогично, время закрытия прошлой полуночи заставляет вас смотреть на следующий день:
Например, чтобы отобразить часы пятницы, мы должны посмотреть на четверг и субботу, поэтому мы можем игнорировать ночной переполнение четверга и правильно сообщить время закрытия пятницы в 2 часа ночи.
Джава
xxxxxxxxxx
1
5pm 1am 5pm 1am 5pm
2
v v v v v
3
000000000000000001111111110000000000000001111111110000000000000001111111
4
\______________________/\______________________/\______________________/
5
Thurs Friday Saturday
Опять подумайте, как бы вы подошли к этому.
Для простоты не обращайте внимания на случай, когда продавец работает 24 часа в сутки, но используйте все остальные возможности. Соблазнительно делать особые случаи для полуночных открытий и ночных закрытий. Но можем ли мы их избежать?
Давайте возьмем график на целую неделю и торговца с обоими крайними случаями:
Рубин
xxxxxxxxxx
1
# A full week of daily hours of operation
2
# This is what would be returned by a database query
3
#
4
hours = [
5
'000000000000111000001111', # Mon: 12pm - 3pm, 8pm - 12am
6
'000000000000111000001111', # Tue: 12pm - 3pm, 8pm - 12am
7
'000000000000111000001111', # Wed: 12pm - 3pm, 8pm - 12am
8
'000000000000111000000000', # Thu: 12pm - 3pm
9
'111100000000000000000011', # Fri: 12am - 4am, 10pm - 4am
10
'111100000000000000000011', # Sat: 10pm - 4am
11
'111100000000000000000000' # Sun: Closed
12
].map { |h| h.chars.map(&:to_i) }
Важнейшее наблюдение - правило без исключений - заключается в следующем: интервалы времени, которые мы отображаем в данный день, - это именно те интервалы, левая конечная точка которых содержится в этом дне.
Наш алгоритм тогда будет:
- Выровняйте ввод, чтобы нам не приходилось беспокоиться об отдельных днях.
- Дополните ввод, чтобы нам не приходилось беспокоиться о полуночи или переполнении.
- Застегните все действительные времена открытия со всеми действительными временами закрытия .
- Сгруппируйте результаты по дням, чтобы восстановить «дневной» вид.
Вот и все - всего пара небольших изменений, чтобы наша оригинальная идея работала, несмотря на особые случаи.
Взятие всех действительных времен закрытия работает, потому что zip метод ruby по умолчанию игнорирует дополнительные элементы:
Рубин
xxxxxxxxxx
1
[1, 2].zip([3, 4, 5, 6])
2
#=> [[1, 3], [2, 4]]
4
# NOTE: extras 5 and 6 are ignored
Используя hours вышеописанное, мы объединим уловки, которые мы изучили до сих пор: модульная арифметика для захвата 24-часового цикла каждого дня, «заполнение» конечных точек недели, чтобы сделать ее круговой, и модульная арифметика снова для обработки 24 до 12 часов преобразования времени.
Рубин
xxxxxxxxxx
1
# make the hours circular, to avoid special casing Monday
2
# at midnight or late night Sunday overlowing into Monday
3
circular_hours = hours.last + hours.flatten + hours.first
4
# this makes two adjustments:
6
# 1. adds 1 to found indexes, because searching for '01'
7
# or '10' returns the index before the one we want
8
# 2. subtracts 24 to remove the extra "circular" Sunday
9
# we added to the beginning in "circular_hours"
10
def all_adjusted_indexes(arr, subarr)
11
all_indexes(arr, subarr).map { |x| x + 1 - 24 }
12
end
13
# all valid open times for a week
15
#
16
# this filters out our extra "padding" days
17
open_times = all_adjusted_indexes(circular_hours, [0,1])
18
.select { |x| (0...24*7).cover?(x) }
19
# all valid close times for a week
21
close_times = all_adjusted_indexes(circular_hours, [1,0])
22
.select { |x| x > open_times.first }
23
# the heart of algorithm
25
#
26
# we zip open and close times, group the "left endpoints"
27
# by day of week, and apply human friendly formatting
28
hours_by_day = open_times.zip(close_times)
29
.group_by { |x| (x[0] / 24).floor }
30
.transform_values { |x| x.map(&human_hours).join(', ') }
31
# all the rest is just printing our results
33
days = %w(Mon Tue Wed Thu Fri Sat Sun)
34
hours_of_operation = days.map.with_index do |day, i|
36
"#{day}: #{hours_by_day[i] || 'Closed'}"
37
end
38
puts hours_of_operation.join("\n")
Смотрите все это в действии здесь: попробуйте онлайн!
Давайте вспомним, что мы сделали. Мы перевели проблему, которая потребовала бы особых случаев - обработка часов каждого дня и частичное совпадение между ними - той, в которой все времена открытия и закрытия в неделю обрабатываются одинаково. В этом едином мире решение нашей проблемы стало тривиальным: мы просто собрали все время открытия и закрытия.
Когда мы закончили, мы перевели обратно в наш оригинальный мир использования отдельных дней group_by. Эта уловка перевода проблемы в более простой «мир», ее решения там и ее обратной передачи является обычной в математике и связана с понятием двойственности .
Take-Aways
Когда вы начнете искать особые случаи, вы увидите их повсюду. Ликвидация их тоже не мелочь. Это сделает ваш код более легким для чтения, более простым в обслуживании и, что наиболее важно, менее подверженным ошибкам.
Думайте об этом так: чтобы сделать нетривиальный код надежным, есть две основные стратегии. Один из них - тщательно перечислить и проверить все особые случаи. Если вы пропустили какой-либо из тестов или если какой-либо из ваших тестов неверен или неполон, ваш код не будет выполнен. Другой заключается в том, чтобы исправить вашу проблему, чтобы особые случаи исчезли. Существует гораздо меньше способов потерпеть неудачу с последней стратегией. И гораздо меньше кода для поддержки.
Не всегда возможно упростить проблему, переписав ее. Но часто это так, хотя бы частично. Итак, когда вы обнаружите, что печатаете if... остановитесь и сделайте паузу на мгновение. Ищите другое решение. Это может быть проще, чем вы думали.
Дополнительные примечания
Вот полезные функции, которые мы использовали в последнем примере часов торговца:
Рубин
xxxxxxxxxx
1
# NOTE: Utility function definitions
2
# utility to find all indexes of subarr in arr
4
def all_indexes(arr, subarr)
5
arr.each_cons(subarr.size).map.with_index do |x, i|
6
x == subarr ? i : nil
7
end.compact
8
end
9
# utility to convert 24 hour time to 12 hour time
11
#
12
# using odd? generalizes this, so it works for
13
# 36 hours, 48 hours, etc
14
to_12h = ->(military) do
15
pm, h = military.divmod(12)
16
"#{h == 0 ? 12 : h}#{pm.odd? ? 'pm' : 'am'}"
17
end
18
# converts an array of 24h [open, close] intervals to:
20
# a hyphenated string range in 12h format
21
# eg: [12, 16] becomes "12pm - 4pm"
22
human_hours = ->(arr) { arr.map(&to_12h).join(' - ') }