И еще раз о задачке про ip-диапазоны.
Собственно, описание задачи и варианты её решения можно почитать здесь у 
nponeccop. Один из вариантов там предложен на CL лавсанчиком. Собственно, он меня немножечко возмутил, поэтому пришлось писать этот пост :)
Суть токова: это вполне себе рабочий код, но так на common lisp писать не надо :) Потому что так надо писать на си. На сях этот же код будет вдвое короче (хотя бы за счет отсутствия скобок и более лаконичного синтаксиса) и вдвое быстрее.
Писать руками такую простыню низкоуровнего кода на CL -- это явный провал. На лиспе надо писать программу, которая будет генерировать низкоуровневый код, это ежу понятно.
Условия нам благоприятсвуют: диапазоны грузятся один раз, а дальше только лукап. Поэтому мы попробуем решить эту задачу классическим лисповым способом: «расставить скобки вокруг спецификации и заставить её запуститься». Вот прямо так, буквально. Итак, имеем файл ranges.list такого вида:
Отлично, давайте расставим вокруг скобки, чтобы получить ranges.list.lisp:
Только, конечно же, не руками, а вот так:
Переходим ко второму этапу: надо заставить полученную скобочную спецификацию компилироваться. Давайте сначала быстренько распарсим строчку ip-адреса и диапазона, плюнем на перфоманс:
Работать это должно так:
Теперь надо немного пораскинуть мозгами. Вот у нас есть диапазон, заданный ip-адресами, каждый из которых представлен четырьмя октетами -- в нашем случае '(104 72 221 173) и '(220 57 219 35). Допустим, нам выдали адрес в таком же формате: ip = (list ip-0 ip-1 ip-2 ip-3); какой код должен быть в программе, которым можно проверить принадлежность этого адреса заданному диапазону? Собственно, тут даже не надо ничего делать руками (например, склеивать октеты в 32-х битный адрес и т.п.), просто тупо сгенерируем сравнение в лесенкой столбик :)
Ну а теперь у нас есть все для того, чтобы "скомпилировать спецификацию":
Вуаля:
Итак, еще раз, что мы сейчас сделали:
Красотища? Да, но пока что не особо.
Собственно, все это я выношу в следующий пост: суперкомпиляция условий, сегментация и препроцессинг кода и так далее. В идеале мы должны не только решить задачу, а еще и получить самый производительный код.
nponeccop. Один из вариантов там предложен на CL лавсанчиком. Собственно, он меня немножечко возмутил, поэтому пришлось писать этот пост :)Суть токова: это вполне себе рабочий код, но так на common lisp писать не надо :) Потому что так надо писать на си. На сях этот же код будет вдвое короче (хотя бы за счет отсутствия скобок и более лаконичного синтаксиса) и вдвое быстрее.
Писать руками такую простыню низкоуровнего кода на CL -- это явный провал. На лиспе надо писать программу, которая будет генерировать низкоуровневый код, это ежу понятно.
Условия нам благоприятсвуют: диапазоны грузятся один раз, а дальше только лукап. Поэтому мы попробуем решить эту задачу классическим лисповым способом: «расставить скобки вокруг спецификации и заставить её запуститься». Вот прямо так, буквально. Итак, имеем файл ranges.list такого вида:
104.72.221.173,220.57.219.35 16.65.26.150,133.42.154.151 80.241.37.220,93.109.90.13 35.165.212.97,105.166.11.16 122.143.149.115,246.17.13.31 20.44.170.80,144.105.12.169 122.132.114.84,184.165.60.95 102.111.151.45,120.152.236.26 53.252.70.24,171.51.24.110 101.103.12.180,224.55.178.136 |
Отлично, давайте расставим вокруг скобки, чтобы получить ranges.list.lisp:
(in-package :ip-ranges) (gen-test-proc "104.72.221.173,220.57.219.35" "16.65.26.150,133.42.154.151" "80.241.37.220,93.109.90.13" "35.165.212.97,105.166.11.16" "122.143.149.115,246.17.13.31" "20.44.170.80,144.105.12.169" "122.132.114.84,184.165.60.95" "102.111.151.45,120.152.236.26" "53.252.70.24,171.51.24.110" "101.103.12.180,224.55.178.136" ) |
Только, конечно же, не руками, а вот так:
(defun preprocess-ranges-file (filename)
(let ((lisp-file (format nil "~a.lisp" filename)))
(with-open-file (f-in filename)
(with-open-file (f-out lisp-file
:direction :output
:if-exists :supersede
:if-does-not-exist :create
:external-format :ascii)
(format f-out "(in-package :ip-ranges)~%(gen-test-proc~%")
(iter (for range in-stream f-in using #'read-line)
(format f-out " \"~a\"~%" range))
(format f-out ")~%~%")))
lisp-file)) |
Переходим ко второму этапу: надо заставить полученную скобочную спецификацию компилироваться. Давайте сначала быстренько распарсим строчку ip-адреса и диапазона, плюнем на перфоманс:
(defpackage #:ip-ranges
(:use :cl :iterate :metatilities)
(:shadowing-import-from :metatilities #:minimize #:finish)
(:export #:check))
(in-package :ip-ranges)
(defun extract-values (string)
(unless (zerop (length string))
(multiple-value-bind (value rest-index)
(parse-integer string :junk-allowed t)
(if value
(cons value (extract-values (subseq string rest-index)))
(extract-values (subseq string 1)))))) |
Работать это должно так:
IP-RANGES> (extract-values "104.72.221.173,220.57.219.35") (104 72 221 173 220 57 219 35) |
Теперь надо немного пораскинуть мозгами. Вот у нас есть диапазон, заданный ip-адресами, каждый из которых представлен четырьмя октетами -- в нашем случае '(104 72 221 173) и '(220 57 219 35). Допустим, нам выдали адрес в таком же формате: ip = (list ip-0 ip-1 ip-2 ip-3); какой код должен быть в программе, которым можно проверить принадлежность этого адреса заданному диапазону? Собственно, тут даже не надо ничего делать руками (например, склеивать октеты в 32-х битный адрес и т.п.), просто тупо сгенерируем сравнение в лесенкой столбик :)
(defun ip-range (range-string)
(let ((values (extract-values range-string))
(vars '(ip-0 ip-1 ip-2 ip-3)))
(assert (= (length values) 8))
(labels ((stairs (cmp values vars)
(if (null values)
t
`(or (,cmp ,(car vars) ,(car values))
(and (= ,(car vars) ,(car values))
,(stairs cmp (cdr values) (cdr vars)))))))
`(and ,(stairs '> (subseq values 0 4) vars)
,(stairs '< (subseq values 4 8) vars))))) |
IP-RANGES> (ip-range "104.72.221.173,220.57.219.35")
(AND
(OR (> IP-0 104)
(AND (= IP-0 104)
(OR (> IP-1 72)
(AND (= IP-1 72)
(OR (> IP-2 221)
(AND (= IP-2 221)
(OR (> IP-3 173) (AND (= IP-3 173) T))))))))
(OR (< IP-0 220)
(AND (= IP-0 220)
(OR (< IP-1 57)
(AND (= IP-1 57)
(OR (< IP-2 219)
(AND (= IP-2 219)
(OR (< IP-3 35) (AND (= IP-3 35) T))))))))) |
Ну а теперь у нас есть все для того, чтобы "скомпилировать спецификацию":
(defmacro gen-test-proc (&rest ranges)
`(defun ip-check (ip-0 ip-1 ip-2 ip-3)
(or ,@(mapcar #'ip-range ranges))))
(defun check (ip-string)
(apply #'ip-check (extract-values ip-string))) |
Вуаля:
IP-RANGES> (load (compile-file (preprocess-ranges-file #p"ranges.list"))) ; compiling file "/home/swizard/devel/lisp/ip-ranges/ranges.list.lisp" (written 03 NOV 2011 11:16:02 PM): ; compiling (IN-PACKAGE :IP-RANGES) ; compiling (GEN-TEST-PROC "104.72.221.173,220.57.219.35" ...) ; /home/swizard/devel/lisp/ip-ranges/ranges.list.fasl written ; compilation finished in 0:00:00.045 T IP-RANGES> (check "192.168.0.1") T IP-RANGES> (check "10.0.0.0") NIL |
Итак, еще раз, что мы сейчас сделали:
- Расставили скобки вокруг списка ip-диапазонов.
- Сгенерировали по описанию функцию ip-check, решающую задачу.
- ...
- Profit!
Красотища? Да, но пока что не особо.
- Несмотря на константные проверки и восьмибитную сегментацию адреса, у нас получилась последовательная проверка.
- Несмотря на автоматическую генерацию условия по диапазону, это условие генерируется какое-то кривоватое и сильно избыточное.
- Несмотря на то, что какие-то диапазоны проверять нет смысла, так как они "поглощаются" более широкими, все равно проверяются все.
- По условиям задачи диапазонов могут быть сотни: поэтому код надо сегментировать по функциям, чтобы не нагнуть компилятор при стратегии (optimize (speed 3))
Собственно, все это я выношу в следующий пост: суперкомпиляция условий, сегментация и препроцессинг кода и так далее. В идеале мы должны не только решить задачу, а еще и получить самый производительный код.
