Войти в систему

Home
    - Создать дневник
    - Написать в дневник
       - Подробный режим

LJ.Rossia.org
    - Новости сайта
    - Общие настройки
    - Sitemap
    - Оплата
    - ljr-fif

Редактировать...
    - Настройки
    - Список друзей
    - Дневник
    - Картинки
    - Пароль
    - Вид дневника

Сообщества

Настроить S2

Помощь
    - Забыли пароль?
    - FAQ
    - Тех. поддержка



Пишет kouzdra ([info]kouzdra)
@ 2009-09-15 03:55:00
Previous Entry  Add to memories!  Tell a Friend!  Next Entry
splay tree
Интересно - а subj какое-то распространение реальное получил,
Или так и осталось красивой идеей?

(Добавить комментарий)


[info]qwerty
2009-09-15 04:55 (ссылка)
http://www.cs.uiowa.edu/~jones/compress/
http://awards.acm.org/citation.cfm?id=0340141&srt=all&aw=147&ao=KANELLAK (по-моему, авторский восторг несколько преувеличен).
http://www.mirlabs.org/jias/benneji.pdf
Еще есть ручная отводилка памяти в куче.

(Ответить)


[info]ppkk
2009-09-15 14:08 (ссылка)
А что в них хорошо и оригинально?

(Ответить) (Ветвь дискуссии)


[info]kouzdra
2009-09-15 22:07 (ссылка)
Забавная очень поисковая структура. Простая и эффективная. И не очень давно придуманная - что само по себе уже выделяет.

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]ppkk
2009-09-16 16:16 (ссылка)
И чем она лучше придуманных давно?

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]kouzdra
2009-09-16 16:23 (ссылка)
Очень простая и экономная в реализации и обладает интересными "кэширующими" свойствами. Вопрос собственно про то и был, оказались ли ее достоинства настолько интересными, чтобы ей начали пользоваться - вроде оказались.

PS: Ну вот RB-деревья AVL-деревья вытеснили, при том, что их преимущества весьма умеренны.

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]ppkk
2009-09-16 17:15 (ссылка)
RB-деревья AVL-деревья вытеснили
Потому я и спросил о каких-нибудь конкретных достоинствах. Что это за "кэширующие свойства"?
Похоже, самому прочесть легче.

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]kouzdra
2009-09-16 17:27 (ссылка)
Элементы, к которым часто обращаются, "всплывают" поближе к корню. Но лучше есс-но почитать. Тем более, что там все просто.

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]ppkk
2009-09-16 17:53 (ссылка)
Ссылку на FreeBSD я уже прислал.

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]kouzdra
2009-09-16 17:56 (ссылка)
Ну из текста вычучивать свойства этой штуки совсем странно - в вики например вполне неплохая статья:

http://en.wikipedia.org/wiki/Splay_tree

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]ppkk
2009-09-16 18:01 (ссылка)
Ссылка на FreeBSD оттуда.

(Ответить) (Уровень выше)


[info]ppkk
2009-09-16 17:19 (ссылка)
http://fxr.watson.org/fxr/source//sys/tree.h

(Ответить) (Уровень выше)