> 1 <

Автор Сообщение

Яков Замир Кацман (нью)

Members


Статус

50 сообщений

Где: Russia
Род занятий:
Возраст:

#7856   2018-03-10 13:34 GMT+3 часа(ов)      
Ниже приведенный способ интернизации так или сяк работает. Можно ли это сделать как-то не так криво? (как это сделать?) Как сравнить строки с помощью интернизации?

(defpackage :tom
(:use :common-lisp)
(:export #:main #:initsymbol #:init *b*)
)
 
(in-package :tom)
(defvar *b* )
(defun init()
(setf *b* (make-array 20
:initial-contents '(
"<209640086183268229693796400861832682296937964008618326822969379640086183268229693796400861832682296937sadsdf>"
"<19063170525534130133489693796400861832682296937964008618326822969379640086183268229693796400861832682296937f>"
"<18438685652650748328849693796400861832682296937964008618326822969379640086183268229693796400861832682296937v>"
"<17006734566489331366739693796400861832682296937964008618326822969379640086183268229693796400861832682296937b>"
"<16099681527776661137689693796400861832682296937964008618326822969379640086183268229693796400861832682296937a>"
"<15831180732119483729699693796400861832682296937964008618326822969379640086183268229693796400861832682296937c>"
"<14169506888433311173619693796400861832682296937964008618326822969379640086183268229693796400861832682296937v>"
"<13056835862493340327789693796400861832682296937964008618326822969379640086183268229693796400861832682296937b>"
"<12514683278217971613539693796400861832682296937964008618326822969379640086183268229693796400861832682296937t>"
"<11622988084595964206679693796400861832682296937964008618326822969379640086183268229693796400861832682296937q>"
"<10964008618326822969379693796400861832682296937964008618326822969379640086183268229693796400861832682296937w>"
"<9063170525534130133489693796400861832682296937964008618326822969379640086183268229693796400861832682296937d>"
"<8438685652650748328849693796400861832682296937964008618326822969379640086183268229693796400861832682296937r>"
"<7006734566489331366739693796400861832682296937964008618326822969379640086183268229693796400861832682296937f>"
"<6099681527776661137689693796400861832682296937964008618326822969379640086183268229693796400861832682296937g>"
"<5831180732119483729699693796400861832682296937964008618326822969379640086183268229693796400861832682296937h>"
"<416950688843331117361i9693796400861832682296937964008618326822969379640086183268229693796400861832682296937>"
"<305683586249334032778y9693796400861832682296937964008618326822969379640086183268229693796400861832682296937>"
"<251468327821797161353u9693796400861832682296937964008618326822969379640086183268229693796400861832682296937>"
"<162298808459596420667u9693796400861832682296937964008618326822969379640086183268229693796400861832682296937>"
 
)
)
)
)
 
(defun initsymbol()
(dotimes (n (array-total-size *b*))
(intern (aref *b* n))
)
)
 
(defun main()
(find-symbol "<162298808459596420667u9693796400861832682296937964008618326822969379640086183268229693796400861832682296937>")
)
 
(in-package :tom)
(tom::init)
(tom::initsymbol)
(tom::main)

отредактировал(а) Яков Замир Кацман (нью): 2018-03-10 22:33 GMT+3 часа(ов)

skelter

Members


Статус

56 сообщений

Где: ---
Род занятий:
Возраст:

#7857   2018-03-10 23:36 GMT+3 часа(ов)      
А можно поподробней описать задачу?

Наверно, я бы в какой-то особый пакет интернил. Потому что в текущем и main будет, и все символы из cl-user, а не только эти длинные строки.

А вообще, мне страшно было бы интернить. Как у Довлатова:
Цитата
Дело было на лекции профессора Макогоненко. Саша Фомушкин увидел, что Макогоненко принимает таблетку. Он взглянул на профессора с жалостью и говорит:
– Георгий Пантелеймонович, а вдруг они не тают? Вдруг они так и лежат на дне желудка? Год, два, три, а кучка все растет, растет...
Профессору стало дурно.

Непонятно, пойдут ли эти символы в мусор, и если да — что для этого надо сделать.

Яков Замир Кацман (нью)

Members


Статус

50 сообщений

Где: Russia
Род занятий:
Возраст:

#7858   2018-03-10 23:42 GMT+3 часа(ов)      
Идея была простая. Узнав что возможно интерпретатор следит за уникальностью всех символов, меня заинтересовал процесс их сравнения. Оказалось что в реальности мы сравниваем не имена, а значения (которые по сути выступают как имена), примерно как я сделал это ниже. Мне осталось пока не понятным воспринимает ли лисп *p* и *t* как один и тот же символ. Это главный вопрос. Как это выяснить?
В каком-то смысле это простая и прозрачная идея.
 
(defpackage :tom
(:use :common-lisp)
(:export #:main #:init)
)
 
(in-package :tom)
(defvar *p*)
(defvar *b*)
(defvar *c*)
(defvar *d*)
(defvar *t*)
(defun init()
(setf *d*
(list
:one "1"
:two "2"
:free "3"
:six "6"
)
)
(setf *c*
(list
:one "1"
:two "2"
:free *d*
)
)
 
(setf *p*
(list
:one *c*
:two *c*
:free *c*
)
)
(setf *b*
(list
:one *c*
:two *c*
:free *d*
)
)
(setf *t*
(list
:one *c*
:two *c*
:free *c*
)
)
 
)
 
(defun main()
(progn
(format t " p == b ~S ~%" (equalp *p* *b*))
(format t " p == t ~S ~%" (equalp *p* *t*))
(format t " d == c ~S ~%" (equalp *d* *c*))
)
)
 
(in-package :tom)
(tom::init)
(tom::main)

отредактировал(а) Яков Замир Кацман (нью): 2018-03-11 19:56 GMT+3 часа(ов)

skelter

Members


Статус

56 сообщений

Где: ---
Род занятий:
Возраст:

#7859   2018-03-10 23:47 GMT+3 часа(ов)      
Короче, понятнее не стало. Лично я в качестве множества строк юзал бы хеш-таблицу.

Яков Замир Кацман (нью)

Members


Статус

50 сообщений

Где: Russia
Род занятий:
Возраст:

#7860   2018-03-10 23:53 GMT+3 часа(ов)      
У меня 120 ГБ xml файл. Если я научусь сравнивать не строки в символы, то это значительно ускорит его обработку. Вопрос: воспринимает ли лисп *p* и *t* как один и тот же символ. по сути вопрос какую стратегию сравнения интерпретатор выберет... У меня есть строка (или дерево) и я хочу узнать не находится ли оно среди уже известных мне строк(деревьев) по возможности очень быстро. Как-то так.

skelter

Members


Статус

56 сообщений

Где: ---
Род занятий:
Возраст:

#7861   2018-03-11 05:28 GMT+3 часа(ов)      
Я бы сказал, это хак. Чтобы функция не возвращала "видел" для строки "MAIN", нужно интернить в особый пакет. Для него надо подобрать имя, чтобы ни с чем не конфликтовало. Будут ли эти символы собраны сборщиком (после удаления пакета?), или же они утекают — не очень ясно.

Другой способ — заводим хеш-таблицу
(defvar *seen* (make-hash-table :test 'equal))

и совершенно стандартным образом с ней работаем. Если строки не нужны, присваеваем *seen* значение nil, таблица уходит в мусор. Конечно, можно и лексическую переменную использовал.

Что быстрее, и насколько — надо мерить, конечно.

skelter

Members


Статус

56 сообщений

Где: ---
Род занятий:
Возраст:

#7862   2018-03-11 05:32 GMT+3 часа(ов)      
Зачем там в примере (symbol-value '*c*) вместо *c* и т. п. — не понял.

Яков Замир Кацман (нью)

Members


Статус

50 сообщений

Где: Russia
Род занятий:
Возраст:

#7863   2018-03-11 12:28 GMT+3 часа(ов)      
(setf *d* (list :one "1"))
(setf *c* (list :one "1"))
(setf *p* (list :one (symbol-value '*d*))
(setf *b* (list :one (symbol-value '*c*))


для того что бы p было равно b (как по факту и есть)

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

skelter

Members


Статус

56 сообщений

Где: ---
Род занятий:
Возраст:

#7864   2018-03-11 19:08 GMT+3 часа(ов)      
Цитата
Как сделать так что бы лисп делал выводы о равенстве по значению указателей на строки


Очевидно, сравнивать с помощью eq. Или вы хотите завернуть строки в списки и сравнивать списки по equal, но чтобы строки сравнивались по eq?

Офтопик: последние две строчки — это ровно то же, что
(setf *p* (list :one *d*))
(setf *b* (list :one *c*))

И так трудно въехать, а тут ещё symbol-value до кучи.

Яков Замир Кацман (нью)

Members


Статус

50 сообщений

Где: Russia
Род занятий:
Возраст:

#7865   2018-03-11 19:31 GMT+3 часа(ов)      
так eq не сравнивает (ни списки - ни символы)
 
 
(defvar *d* )
(defvar *p* )
 
(setf *d* (list :one "1"))
(setf *p* (list :one "1"))
 
(eq *d* *p*) => NIL


"Returns true if its arguments are the same, identical object; otherwise, returns false."


"two similar lists are usually not identical."
http://www.lispworks.com/documentation/lw51/CLHS/Body/f_eq.htm

Они не идентичны...

(Упростил)

отредактировал(а) Яков Замир Кацман (нью): 2018-03-11 20:11 GMT+3 часа(ов)

skelter

Members


Статус

56 сообщений

Где: ---
Род занятий:
Возраст:

#7866   2018-03-11 20:09 GMT+3 часа(ов)      
eq сравнивает указатели как раз. На числах и литерах, правда, ведёт себя непредсказуемо, так что имеет смысл использовать eql вместо него. А строка — это массив. Массивы вполне нормально сравнивать по указателю.

*d* и *p* получены разными вызовами функции list, поэтому это разные конс-ячейки, поэтому они не eq. Я и спрашиваю: вы хотите иметь возможность сравнивать соответствующие элементы списков по указателям, то есть с помощью eq?

В любом случае, (eq "1" "1") вполне может дать nil (не знаю, обязательно это или нет). То есть сравнение по указателям тут не работает.

Короче говоря, если вам всё время поступают новые строки, которые вы собираетесь интернить, по-моему, имеет смысл вместо этого использовать хеш-таблицу. И если производительность будет неудовлетворительная, переписать через символы. Хотя сомневаюсь, что через символы будет быстрее: неясно, почему превращение строки в символ должно быть дешевле, чем посмотреть эту строку в хеше.

Если же вы хотите сразу загнать кучу строк в символы и потом многократно использовать эти символы... Хозяин — барин, конечно, но я бы всё равно сначала сделал через хеш, или через string= , а потом бы думал, если бы получилось медленно.

antares0

Members


Статус

185 сообщений

Где: Russia
Род занятий:
Возраст:

#7867   2018-03-11 21:08 GMT+3 часа(ов)      
Цитата
Яков Замир Кацман (нью) :
Как сделать так что бы лисп делал выводы о равенстве по значению указателей на строки, а не по содержимому самих строк?


В стандарте - это называется sxhash
 
(equal x y) implies (= (sxhash x) (sxhash y))

antares0

Members


Статус

185 сообщений

Где: Russia
Род занятий:
Возраст:

#7868   2018-03-11 21:19 GMT+3 часа(ов)      
Цитата
Яков Замир Кацман (нью) :
Ниже приведенный способ интернизации так или сяк работает. Можно ли это сделать как-то не так криво?

Напрашивается
(mapcar #'intern '("A11" "B22" "C33 ...))

skelter

Members


Статус

56 сообщений

Где: ---
Род занятий:
Возраст:

#7869   2018-03-12 00:27 GMT+3 часа(ов)      
По равенству значений хеш-функции нельзя же сделать вывод о равенстве (в любом смысле) объектов.

antares0

Members


Статус

185 сообщений

Где: Russia
Род занятий:
Возраст:

#7870   2018-03-12 10:32 GMT+3 часа(ов)      
Цитата
skelter :


А какое другое применение ты предлагаешь для этих значений?
Применительно к sxhash это равенство заложено сразу в определении. Зря я что ли ссылку на стандарт давал.

skelter

Members


Статус

56 сообщений

Где: ---
Род занятий:
Возраст:

#7871   2018-03-12 21:06 GMT+3 часа(ов)      
В смысле какое применение? Наверно, реализаторам для хешей. (Я вообще эту функцию вижу в первый раз, сколько нам открытий чудных... )

Ведь в хеше могут встретиться ключи с одинаковым значением хеш-функции. Соответственно, в стандарте написано, что equal-равенство влечёт равенство значение хеш-функции, а про импликацию в обратном направлении ничего нет.

antares0

Members


Статус

185 сообщений

Где: Russia
Род занятий:
Возраст:

#7872   2018-03-12 21:33 GMT+3 часа(ов)      
У меня ощууение что ты не читал описание из стандарта по ссылке (не смог?). Но зачем-то выдумываешь. В таком ключе общение смысла не имеет

Яков Замир Кацман (нью)

Members


Статус

50 сообщений

Где: Russia
Род занятий:
Возраст:

#7873   2018-03-12 22:01 GMT+3 часа(ов)      
Не ругайте вы друг друга (это похоже на начало шансона, без продолжения)
Давайте лучше делится знаниями. Знающих людей и так мало, что бы они еще и грызлись.
Не обижайте друг друга!

(Там контрольная сумма высчитывается. Она уникальна. 'Ведь в хеше могут встретиться ключи с одинаковым значением хеш-функции' - НЕ МОГУТ)

skelter

Members


Статус

56 сообщений

Где: ---
Род занятий:
Возраст:

#7874   2018-03-12 22:24 GMT+3 часа(ов)      
> У меня ощууение что ты не читал описание из стандарта по ссылке (не смог?).

Я умею читать. А что конкретно я упустил?

> Но зачем-то выдумываешь.

Что выдумываю?

> В таком ключе общение смысла не имеет

Не, всё нормально. Я доброжелательный и не совсем тупой, просто мы где-то друг друга недопоняли.

> Она уникальна.

Где это написано?

> 'Ведь в хеше могут встретиться ключи с одинаковым значением хеш-функции' - НЕ МОГУТ

Стандарт, естественно, не диктует, какой алгоритм хеширования использовать. Но вообще в компьютер саенс — могут.
https://ru.wikipedia.org/wiki/Хеш-таблица
https://ru.wikipedia.org/wiki/Коллизия_хеш-функции

skelter

Members


Статус

56 сообщений

Где: ---
Род занятий:
Возраст:

#7875   2018-03-12 22:31 GMT+3 часа(ов)      
Вот, кстати, неконструктивное доказательство неинъективности функции sxhash в любой реализации лиспа.

Эта функция может принимать любой объект (Exceptional Situations: None.) и возвращает неотрицательный fixnum. Значит, число возможных значений этой функции не превосходит most-positive-fixnum + 1. Если рассмотреть любое множество из most-positive-fixnum + 2 объектов (например, это могут быть все неотрицательные fixnum-ы и число -1), то согласно принципу Дирихле хотя бы два объекта будут иметь одинаковый хеш.

Яков Замир Кацман (нью)

Members


Статус

50 сообщений

Где: Russia
Род занятий:
Возраст:

#7876   2018-03-13 01:25 GMT+3 часа(ов)      
Да, коллизия говорят вероятна для случайного набора знаков. Для осмысленной инфорации вероятность колизии вроде бы падает. Это сложный вопрос. В любом случае, тут речь была совсем о другом. Как максимально автоматизировать эту процедуру средствами интерпретатора.

skelter

Members


Статус

56 сообщений

Где: ---
Род занятий:
Возраст:

#7877   2018-03-13 03:33 GMT+3 часа(ов)      
> Как максимально автоматизировать эту процедуру средствами интерпретатора.

Может, написать процедуру? (Функцию.) Вообще, я так и не понял, о какой процедуре речь, сдаюсь. Наверно, контекста мало. Что знал, уже написал.

Яков Замир Кацман (нью)

Members


Статус

50 сообщений

Где: Russia
Род занятий:
Возраст:

#7878   2018-03-13 18:04 GMT+3 часа(ов)      
Основной алгоритм:

1) Создать множество (hash set) строк
2) Создать индекс(ы) и сортировать.
3) Проверить, что строка (как последовательность символов), с которой вы имеете дело, уже в множестве
4) Если да, то использовать строку из множества
5) В противном случае, добавить эту строку в множество и затем использовать ее шаг 2)
6) создать соответствующее API

(взято с https://habrahabr.ru/post/260767/)

Вы правы. Значит надо будет написать.

skelter

Members


Статус

56 сообщений

Где: ---
Род занятий:
Возраст:

#7879   2018-03-14 03:16 GMT+3 часа(ов)      
Ну, вот пример:
(let ((cache (make-hash-table :test 'equal)))
(dolist (string strings)
(if (gethash string cache)
(do-stuff string)
(setf (gethash string cache) t))))

В стоимость включена возможность ассоциирования со строками каких-то значений. В таком случае будет корректнее тест
if (nth-value 1 (gethash string cache))

отредактировал(а) skelter: 2018-03-14 03:26 GMT+3 часа(ов)
> 1 <


Онлайн :

0 пользователь(ей), 10 гость(ей) :




Реклама на сайте: