Объявление для зашедших случайно

Сюда я складываю разные мелкие заметки по программированию: эдакая локальная база знаний в отдельно взятом мозге.

Вряд ли мои записи будут интересны кому-нибудь, кроме меня самого.

Увеличить размер history

Чтобы увеличить размер history в Ubuntu, достаточно добавить две строчки в файл ~/.bashrc:

# увеличение размера истории
export HISTSIZE=2000
export HISTFILESIZE=2000

Печать из Linux в Windows

Задача: печатать из Linux на принтере Canon, к которому под Linux нет драйверов. Принтер подключён к компьютеру, который работает под Windows.

Решение.

1. На компьютере с Windows ставим четвёртый акробат. Файл называется acrobat405.exe, где я его нашёл, уже не помню.

2. Пишем нехитрый CGI-скрипт на newLISP, который будет по команде снаружи брать файл из указанной папки и печатать его. Скрипт я назвал printit.cgi

--- Начало printit.cgi ---

#!c:\pdfpipe\NewLisp.exe

(module "cgi.lsp")



(set 'pool-path "C:\\pdfpipe\\pdfpool\\") ;

(set 'acrobat-path "\"c:\\Program Files\\Adobe\\Acrobat 4.0\\Reader\\AcroRd32.exe\"")

(set 'printer-name "OneNote")



(set 'file-to-print (CGI:get "file"))



(exec (append acrobat-path " /t /n " pool-path file-to-print " " printer-name))

(exec (append "del " pool-path file-to-print))
--- Конец printit.cgi ---

Как можно заметить, в скрипте указан путь к Акробату и путь к расшаренной папке, куда будут скидываться файлы из Linux. Наверное, излишне говорить, что для работы скрипта нужен установленный в папку c:\pdfpipe\NewLisp.exe.

3. Делаем батничек start.bat с единственной строчкой внутри:

start /b newlisp.exe newlisp -c -d 8003

4. Делаем батничек startup.vbs, который будет запускать start.bat тихо, не нервируя пользователя. Внутри батничка уже две строчки:

Set oShell = WScript.CreateObject("WScript.Shell")

oShell.Run "server.bat", 0, False

5. Создаём папку для документов и расшариваем её.

6. Дальше работаем на компьютере с Linux. Подразумевается, что cups-pdf и lynx у нас установлены.

7. Открываем файл /etc/cups/cups-pdf.conf. Сообщаем, что печатать теперь надо в другую папку: вместо «Out ${HOME}/PDF» пишем «Out /var/spool/pdfprint». Папку /var/spool/pdfprint надо будет создать и проставить на неё разрешения.

8. Ближе к концу cups-pdf.conf вставляем вместо закомментированного PostProcessing строчку «PostProcessing /var/spool/pdfprint/script.lsp»

9. А вот и сам файлик script.lsp:

--- Начало script.lsp ---
#!/usr/bin/newlisp

(set 'pdf-path "/var/spool/pdfprint/")

(dolist (x (directory pdf-path "\\.pdf"))
(exec (append "mv " pdf-path x " " pdf-path "pool"))
(exec (append "lynx 192.168.25.101:8003/printit.cgi?file=" x " -dump")))

(exit)
--- Конец script.lsp ---

Где править айпишник видно. Это айпишник компьютера с Windows к которому подключён принтер.

10. Тонкий момент. С помощью apparmor надо разрешить cups-pdf печатать в выбранную нами папку. Как именно это сделать я уже забыл, но в Интернетах про это много.

11. Наконец, надо подсоединить сетевую папку. В /etc/fstab пишем что-то типа:
//192.168.25.101/canon /var/spool/pdfprint/pool cifs rw,user=print,pass=print,iocharset=utf8,file_mode=0777,file_mode=0777,dir_mode=0777

Зачем два раза писать file_mode не спрашивайте. У меня стоит так и работает. Наверное, будет работать и с одним file_mode, но мне было лень проверять.

12. Вот, в общем, и всё. На всякий случай, как всё работает.

а) Печатаем в PDF
б) файл blablabla.pdf кладётся в /var/spool/pdfprint
в) исполняется скрипт /var/spool/pdfprint/script.lsp
г) Скрипт кладёт файл blablabla.pdf в сетевую папку /var/spool/pdfprint/pool
д) Скрипт через lynx даёт команду cgi-скрипту на компьютере windows печатать файл blablabla.pdf
е) Скрипт printit.cgi запускает акробат, чтобы тот напечатал blablabla.pdf и стирает файл.

13. Инструкцию пишу по памяти. Прямо сейчас у меня всё работает, но, вполне вероятно, про какую-то мелочь я забыл упомянуть.

CentOS, crypto.lsp

Модуль crypto.lsp не заработал сразу. Так как для него нужна библиотека libcrypto.so, которая в моём CentOS по умолчанию установлена не была. Проблема решилась в две команды.

Команда первая — выдать список пакетов с этой библиотекой:

yum provides "*/libcrypto.so*"

Команда вторая — установить один из пакетов, содержащих нужную библиотеку:

sudo yum install openssl-devel-0.9.8e-12.el5_4.6.i386

Вуаля.

Скрипты из Windows не запускаются под Linux

Скрипты из Windows не запускались, выдавая ошибку (2)No such file or directory: exec of '.../index.cgi' failed.

Двухчасовое расследование показало, что проблема в DOS-формате скриптов: конец строки обозначался двумя символами, а не одним, поэтому Апач не мог правильно обработать первую строчку.

Установленный vim, однако, не показывал привычного ^M, поэтому я понял это только когда начал сравнивать размеры файлов.

Команда "dos2unix index.cgi" решила проблему.

Установка newLISP на CentOS

Как установить newLISP на CentOS автоматически я не нашёл. Зато замечательно сработала установка через компиляцию исходников:

wget http://www.newlisp.org/downloads/newlisp-10.2.8.tgz
tar -xf newlisp-10.2.8.tgz
cd newlisp-10.2.8
sudo ./configure-alt
sudo make
sudo make install

Ubuntu: переименовать файлы по маске

Мне потребовалось переименовать файлы по маске: заменить файлы вида 1003.123 на 1003.10123. Получилось вот такой командой:

find . -maxdepth 1 -iname "1003.*" -execdir rename "s/1003\./1003\.10/" \{\} \;

При этом maxdepth 1 означает "не спускаться ниже по дереву", а команда rename имеет шаблон "/s/from/to/"

newLISP: curry-all

Обнаружил, что после перехода на новую версию newLISP перестал работать мой curry-all (который должен делать то же самое, что и curry, только с несколькими аргументами). Вот переставший работать вариант:

(context 'curry-all)
(define-macro (curry-all:curry-all f)
  (letex (f1 f lst (map string (args)))
    (fn (z) (eval-string (append "(" (name 'f1) " " (join 'lst " ") " curry-all:z)")))))
(context 'MAIN)

А вот вариант работающий, позаимствованный у Лутца:

(define (curry-all f)
   (append (lambda (z)) (list (cons f (append (args) '(z))))))

Кстати, Лутц предлагает ещё одно решение, вот здесь:
http://newlispfanclub.alh.net/forum/viewtopic.php?f=16&t=3169

newLISP 10.2.8 и Ubuntu 8.10

Установил новую версию newLISP: 10.2.8. Пишет, что ему нужна библиотека libreadline6, а у меня только libreadline5.

Обновил свою 8.10 до 9.04. Не помогло.

Заглянул на newlisp.org. Там Lutz пишет, что можно настроить автоматическую установку newLISP через sudo apt-get install newlisp, но... только в 9.10 и выше.

Мне кажется, это намёк. Сейчас обновлюсь до 9.10 и, очень надеюсь, всё заработает.

Lock: продолжение.

Придумал новый алгоритм для лоченья файлов. Где можно наколоться пока не вижу. Но опыт, конечно, покажет. Также у меня всегда остётся запасной вариант: man 1 flock, man 2 flock.

Допустим, нам надо изменить test.txt

1. Проверяем, нет ли test.txt.lock, изменённого менее 30 секунд назад.

2. Если есть, ждём 100 ms, идём на пункт 1.

3. Стираем лок-файл, изменённый старше 30 секунд:
find . -maxdepth 1 -mmin +0,5 -name test.txt.lock -delete
(Команду надо ещё проверить). Стирать хочется именно одной командой, чтобы во время её выполнения другой скрипт не вставил свой файл.

4. Делаем аппенд к лок-файлу:
(append-file "test.txt.lock" (append id "\n"))

5. Если мы не успели, идём на пункт 1.

6. Мы успели. Делаем необходимые манипуляции с test.txt.

7. Стираем lock-файл.

newLISP: самодельная блокировка текстовых файлов

Проблема. Скрипт создаёт по запросу пользователей текстовые заявки с возрастающими номерами. Если два пользователя одновременно нажмут "создать заявку", может создаться две заявки с одинаковым номером. Тогда у одного из пользователей заявка не сохранится (будет затёрта вторым).

Решение.

1. Делаем в папке с заявками файл lock.

2. Убеждаемся, что генератор случайных чисел сеется. Я сею его на основе выбранного порта и системного времени. Подозреваю, в windows может не работать, если там time-of-day возвращается с точностью до секунды, а не до миллисекунды.

(seed (div (time-of-day) (int (env "REMOTE_PORT")) 0.000001))

3. Вот собственно процедура получения номера. Суть простая. Пишем через append в файл "lock" номер, который мы хотим занять и подписываем его случайным числом. Проверяем, что никто не успел вклиниться перед нами. Если мы опоздали (номер уже занят), повторяем попытку.

(define (occupy-number) (local (id num res)
  (set 'id (rand-string))
  (set 'num (last (or (sort (map int (directory "." "txt$"))) '(0))))
  (do-until (= (or (find (s-a num ":" id) res 0) "no") (find (s-a num ":.*") res 0))
    (inc num)
    (append-file "lock" (s-a num ":" id "\n"))
    (set 'res (read-tail "lock" 100)))
  num))

Я тестировал на одновременных 100 подключениях. Работало с двойным запасом.

4. Вот воспомогательные процедуры:

(define (string-append) (apply append (map string (args))))
(set 's-a string-append)

; В Windows реальный rand (насколько я помню) имеет диапазон в 32768,
; поэтому я его для надёжности "утроил".
(define (rand-string)
  (join (map string (list (rand 65536) (rand 65536) (rand 65536))) "_"))

; Возвращает последние 'lines строк файла в виде списка.
; Работает, по понятным причинам, только под *nix
(define (read-tail fname (lines 10))
  (exec (append "tail " fname " -n " (string lines))))

5. Замечания.

5.1. Лог может сильно разрастись, надо как-то его стирать изредка.

5.2. Если мы стёрли файл, а в lock он остался, в нумерации будут пропуски. Это скорее фича, но тем не менее.

5.3. Процедура блокировки файлов для изменения не проработана. Если мы хотим обезопаситься ещё и от изменения, нужно думать дальше.

5.4. Схема "велосипедна". То есть, лучше бы, вообще, пользоваться базами данных.

JavaScript: закрывать псевдопопап по Escape

Как закрывать псевдопопапы по нажатию Esc.

1. Ставим обработчик в body:

<body onkeydown="if (event.keyCode == 27) closePopup();">

2. Создаём массив, в котором будет храниться список открытых окон:

// Список открытых окон
var popupList = new Array();

3. Запиливаем вот эти функции:

// Закрывает открытое окно
function closePopup() {
  if (popupList.length == 0) return;
  document.getElementById(popupList.pop()).style.display = 'none';
}

// Удаляет элемент из массива
function popAssoc(arr,itm) {
  var arr1 = new Array();
  for (i=0;i<arr.length;i++) {
    if (arr[i] != itm) arr1.push(arr[i]);
  }
  return arr1;
}

// Показывает всплывающее окно по центру экрана рядом с курсором мыши
function showWin(id, event, firstField) {
  // Если окно уже показано, прячем его
  if (document.getElementById(id).style.display == 'block') {
    popupList = popAssoc(popupList,id);
    document.getElementById(id).style.display = 'none';
  } else {
    // Запоминаем окно в списке открытых
    popupList.push(id);
    // Вычисляем координаты
    thisWin = document.getElementById(id);
    thisWin.style.top = getYCoord(parseInt(thisWin.style.height), event);
    thisWin.style.left = (document.body.clientWidth - parseInt(thisWin.style.width)) / 2;
    // Показываем окно
    thisWin.style.display = 'block';
    // Фокусируемся на первом поле
    if (firstField) setFocus(firstField);
  }
}

Про вычисление координат для окна я уже писал раньше:
http://hilocomod.blogspot.com/2010/03/js.html

SICP: малая теорема Ферма

Кусочек кода с распознаванием простых чисел по Малой Теореме Ферма.

; Разное встроенное
(define (even? x) (= (% x 2)))
(define (square x) (* x x))
(define (prime? p) (= (first (factor p)) p))

; Вычисляет (% (pow a b) p)
(define (expmod a b p)
  (cond ((= b) 1)
        ((even? b) (% (square (expmod a (/ b 2) p)) p))
        (true (% (* a (expmod a (dec b) p)) p))))

; Проверяет число на простоту 1 раз
(define (fermat-test p)
  (let (n (+ (rand (- p 1)) 1))
    (= (expmod n p p) n)))

; Проверяет число на простоту много раз
(define (fast-prime p (n 1))
  (local (f)
    (while (and (set 'f (fermat-test p)) (!= (dec n))))
    f))

; Проверяет число на принадлежность к Кармайкловым Числам.
(define (carmaicl? x)
  (and (not (prime? x))
       (apply and (map (fn (n) (= (expmod n x x) n)) (sequence 1 (- x 1))))))

Функция carmaicl? работает довольно медленно. Чтобы прогнать её на числах от 2 до 5 000 потребовалось несколько минут. При этом на проверку 2х функция затрачивает примерно в 2 раза больше времени, чем на проверку х. То есть, если я правильно понимаю, на проверку диапазона 5k-10k уйдёт в три раза больше времени, чем на проверку диапазона 0k-5k.

Uptime в среде Windows

Как известно, uptime в среде Windows можно получить, набрав "net stats server".

Чтобы перевести выдаваемый текст в секунды аптайма, пришлось написать вот такую функцию:

; Показывает Uptime в среде Windows
(define (uptime)
  (let (wt (regex {(\d+)/(\d+)/(\d{4}) (\d+):(\d+) ([AP]M)} (join (exec "net stats server"))))
    (if (= (wt 18) "PM") (setf (wt 12) (+ (int (wt 12)) 12)))
    (- (date-value)
       (* (% (+ 24 (int ((regex {\d+(?=:)} (date)) 0)) (- ((now) 3))) 24) -3600)
       (apply date-value (append (select (map int wt) 9 3 6 12 15) '(0))))))

Комментарии.

1. parse-date не работает в Win32.
2. (date-value параметры) возвращает время GMT. В моём случае разница составила 4 часа. Чтобы скорректировать пришлось отнять часы в (date) от часов в (now).
3. Время выполнения функции — примерно 125 миллисекунд.

SICP 1.19: Фибоначчи по логарифму

Вот эта гнусная функция:

(define (even? x) (if (= (% x 2))))

(define (fib n (a 1) (b 0) (p 0) (q 1))
  (cond ((= n) b)
        ((even? n) (fib (/ n 2)
                        a
                        b
                        (+ (* p p) (* q q))
                        (+ (* 2 p q) (* q q))))
        (true (fib (dec n)
                   (+ (* b q) (* a q) (* a p))
                   (+ (* b p) (* a q))
                   p
                   q))))

Программирования, тут, на мой взгляд, гораздо меньше, чем математики. Думаю, это неправильно.

Чётные числа

Проверил, как быстрее считать чётность.

; Вариант 1, хитропопый
(define (even-1 x)
  (if (find (last (string x)) '("0" "2" "4" "6" "8")) true))

; Вариант 2, "в лоб"
(define (even-2 x)
  (if (= (% x 2))))

Как я и ожидал, вариант "в лоб" оказался примерно на порядок быстрее, да.

SICP: итеративное возведение в степень

Долго думал, как сделать итеративный процесс возведения в степень (SICP, упражнение 1.16). Я сразу догадался, что брать за основу надо число в двоичной системе счисления, но мне было непонятно, как переводить это число в алгоритм.

Вот например, как выглядели алгоритмы и двоичная запись для некоторых чисел:

7 *+*+ 111
8 *** 1000
9 ***+ 1001
10 **+* 1010

В итоге оказалось всё просто. Надо отбрасывать самый первый знак, а дальше трактовать единицу как "возвести в квадрат и умножить", а ноль — как "просто возвести в квадрат".

Также я впервые использовал здесь функцию cons, которая объединяет first и rest.

; Возвести число b в степень p (p должно быть больше 1)
(define (pow-hm b p)
  (apply (fn (x y) (if (= y) (* x x) (* x x b)))
         (cons b (map int (1 (explode (bits p)))))
         2))

А вот то же самое, только по "итеративному алгоритму" предложенному в SICP:

; Возвести b в степень n
(define (pow-sicp-1 b n)
  (cond ((= n 1) b)
        ((= (% n 2)) (pow-sicp-1 (* b b) (/ n 2)))
        (true (* (pow-sicp-1 (* b b) (/ n 2)) b))))

Вроде бы как, ошибиться тут просто негде. Однако… цитирую SICP:

«Храните, помимо значения степени n и основания b, дополнительную переменную состояния a, и определите переход между состояниями так, чтобы произведение abⁿ от шага к шагу не менялось».

Спрашивается, зачем козе баян? Разве что, перехерачить алгоритм вот так:

; То же самое, но с инвариантом
(define (pow-sicp-2 b n (a 1))
  (if (= n 1)
    (* b a)
    (* a (pow-sicp-2 (* b b) (/ n 2) (if (= (% n 2)) 1 b)))))

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

Дополнение.

Блджад. Только перейдя к упражнению 1.17 я понял, в чём была соль. По условиям задачи, у нас есть вот такие функции:

(define (double x) (* x 2))
(define (halve x) (/ x 2))
(define (even? x) (if (= (% x 2))))

Из них надо склепать умножение. Вот труе итеративный вариант:

; Умножить а на b
(define (mul-sicp-i a b (p 0))
  (let (p 0)
    (until (= b 1)
      (set 'p (+ p (if (even? b) 0 a)))
      (set 'a (double a))
      (set 'b (halve b)))
    (+ a p)))

А вот то же самое, но через жопу концевую рекурсию:

; Умножить a на b
(define (mul-sicp-t a b (p 0))
  (if (= b 1)
    (+ a p)
    (mul-sicp-t (double a) (halve b) (+ p (if (even? b) 0 a)))))

Способы разменять монеты

Хитроумный алгоритм по размену монет из первой главы SICP. Мне потребовалось значительное время, чтобы понять как он работает и воспроизвести его:

#
# Число способов разменять n центов монетами по 1, 5, 10, 25 и 50 центов.
# 

; Доступные монеты
(set 'монеты '(1 5 10 25 50))

; Число разменов n центов с помощью c монет.
(define (размены n (c 5))
  (cond ((< n) 0)
        ((= n) 1)
        ((= c 1) 1)
        (true (+ (размены n (- c 1))
                 (размены (- n (монеты (- c 1))) c)))))

Это воссозданный мной алгоритм из книжки. Вначале же я сделал иначе: считал все возможные методы размена, потом через unique отбирал уникальные, потом через memoize добивался терпимой скорости. Тоже работало, плюс кроме числа способов размена я видел в списке ещё и сами способы.

Но решение из книжки, конечно, красивее.

Кстати, в самой книжке алгоритм реализован, на первый взгляд, примерно так же, но там есть слова: «на то, чтобы получить ответ 292 уйдёт какое-то время». В реальности время выполнения процедуры на моём компьютере — 0,3 миллисекунды.

То ли эта фраза писалась в семидесятые года, то ли newLISP гораздо круче чем Scheme.

PS: Разменять доллар можно 292 способами. Способов разменять 10 долларов уже 800 тысяч.

PPS: Те же яйца, но с печатью дерева.

(define (размены n (c 5))
  (print "Р" n " (" c "): ")
  (cond ((< n) (println 0) 0)
        ((= n) (println 1) 1)
        ((= c 1) (println 1) 1)
        (true (println "Р" n " (" (- c 1) ") + Р" (- n (монеты (- c 1))) " (" c ")")
              (+ (размены n (- c 1)) (размены (- n (монеты (- c 1))) c)))))

Хвостовая рекурсия

Немного доброты по ссылке с форума newLISP (Ссылка)

Подводя итог, эта точка зрения на хвостовую рекурсию основана на следующих идеях:

* Она предназначена для избегания циклов, которые по какой-то причине полагаются пуристами "плохими". Эти извращенцы думают в циклах, потом переводят свой код в хвостовую рекурсию, а потом ожидают от компилятора обратного перевода в циклы. Это чисто академическая ментальная гимнастика безо всякой практической цели.

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

* Любой код, который зависит от хвостовой рекурсии, легко может быть переписан в циклах. Такая перепись является тривиальной местной трансформацией.

* Межпроцедурная хвостовая рекурсия может привести к некоторому увеличению производительности, но это увеличение будет крайне мало, и за это увеличение придётся заплатить потерей ценной отладочной информации.

Фриддл, ДКА и НКА

Закончил читать книгу Фриддла про регулярные выражения.

Фриддл, конечно, молодец, сказать нечего. Но про автоматы и про разницу между ними он написал крайне непонятно. Гораздо понятнее вот здесь:

http://www.rsdn.ru/article/alg/nka.xml

Если бы я сначала потратил 10 минут на чтение этого текста, а только потом принялся бы за Фриддла, полагаю, я бы вынес из книги Фриддла гораздо больше пользы.