Ada_Ru форум

Обсуждение языка Ада

[ada_ru] Пакеты реализаций множеств натуральны чисел на языке Ada 2012

Оставить новое сообщение

Сообщения

Sergey Dukov
[ada_ru] Пакеты реализаций множеств натуральны чисел на языке Ada 2012
2017-12-21 09:15:20
Здравствуйте.

Предлагаю два пакета реализаций множеств натуральны чисел на языке Ada 2012

Первый пакет имеет название "set of natural pkg". Реализация множества натуральных чисел этого
пакета построена по алгоритму "двухуровневых битовых карт". Диапазон представляемых чисел - 0 ..
4096*4096 - 1 (что вполне достаточно для представления всех символов Unicode).
Применённый для данного пакета алгоритм эффективно работает на 64-х разрядных системных
архитектурах. На 32-х разрядных системных архитектурах алгоритм будет работать медленно, так как
64-х разрядная арифметика будет эмулироваться, или вообще не будет работать если 64-х разрядная
арифметика запрещена. Я, в своё время, разработал подобный пакет, реализованный по алгоритму
трёхуровневых битовых карт на языке ADA95, который успешно работал на 32-х разрядных системных
архитектурах. Но исходные тексты этого пакета были утеряны. Эффективность подобных алгоритмов
зависит от длины машинного слова. Чем больше длина машинного слова, тем выше эффективность работы
алгоритма. Отсюда вопрос, а работают ли инструкции расширения AVX с битовыми картами? Если да, то
это бы дало большие возможности создания высокоэффективных реализаций алгоритмов работы с
математическими множествами. Если кому-то что-то об этом известно, то пусть мне сообщит.

Второй пакет называется <Comma Separated Set> и представляет собой простенькую реализацию множества
натуральных чисел, где множество представлено текстовой строкой, содержащей список натуральных
чисел, разделённых запятыми. Реализация поддерживает очень ограниченное количество операций над
множеством, но может быть очень полезной при обработке XML-файлов, где множества хранятся как
атрибуты XML-элементов.

Подробности и исходники в статье http://www.rtsdd.ru/set of natural lib.aspx

С уважением и наилучшими пожеланиями, Сергей Дюков.
kazakov1961
[ada_ru] Re: Пакеты реали заций множеств на туральны чисел н а языке Ada 2012
2017-12-21 10:42:03
В моей реализации множеств и отображений Unicode (эквивалент Ada.Strings.Map) используются
упорядоченные интервалы:
  
    http://www.dmitry-kazakov.de/ada/strings_edit.htm#7.9
  
(Эффективность всегда зависит от того какие операции применяются чаще других)
Sergey Dukov
RE: [ada_ru] Re: Пакеты реализаций множеств натуральны чисел н а языке Ada 2012
2017-12-21 12:57:33

From: [email protected] [mailto:[email protected]]
Sent: Thursday, December 21, 2017 1:42 PM
To: [email protected]
Subject: [ada_ru] Re: Пакеты реализаций множеств натуральны чисел н а языке Ada 2012



В моей реализации множеств и отображений Unicode (эквивалент Ada.Strings.Map) используются
упорядоченные интервалы:

http://www.dmitry-kazakov.de/ada/strings_edit.htm#7.9

(Эффективность всегда зависит от того какие операции применяются чаще других)

[Sergey Dukov]

Моя реализация подобна реализации встроенного типа языка MODULA2
SET OF <перечислимый тип>

Где множество представляется множеством бит в памяти компьютера (битовая карта). Для языка MODULA2
такая простая реализация типа
SET OF CARDINAL
практически невозможна. Слишком большая мощность множества, слишком много нужно памяти для битовой
карты, слишком много нужно времени для обработки этой битовой карты.

В моей реализации битовые карты вышележащих уровней описывают массивы битовых карт нижележащих
уровней. В результате, в памяти хранятся лишь те битовые карты, которые не пусты и не заполнены
полностью.

В любом случае, эффективность обработки битовых карт зависит от длины машинного слова. Чем больше
длина машинного слова, тем меньше нужно инструкций процессора типа “move”, “load”, “store”, “or”,
“xor”, “and”, “not” для обработки битовых карт и, следовательно, выше эффективность алгоритма.

Поэтому то у меня был вопрос насчёт инструкций расширения AVX. Я знаю, что инструкции расширения
MMX работают с битовыми картами. Но длина регистра MMX равна 64, так что заморачиваться с MMX
совершенно не имеет смысла. А вот для AVX, где длина шины равна 512?
Vadim Godunko
Re: [ada_ru] Пакеты реализаций множеств натуральны чисел на языке Ada 2012
2017-12-21 13:21:00
On 12/21/2017 12:15 PM, Dukov Sergey [email protected] [ada_ru] wrote:
> 
> Отсюда вопрос, а 
> работают ли инструкции расширения AVX с битовыми картами?

В расширениях инструкций от Intel всегда можно найти все мыслимые 
инструкции. Там правда есть небольшая засада - первая версия очередного 
набора инструкций обычно для маркетологов, а вторая и далее - уже для 
обычных программистов. Поэтому если что-то не хватило в AVX - поищите в 
AVX2. :)


------------------------------------

------------------------------------


------------------------------------

Yahoo Groups Links

<*> To visit your group on the web, go to:
    http://groups.yahoo.com/group/ada_ru/

<*> Your email settings:
    Individual Email | Traditional

<*> To change settings online go to:
    http://groups.yahoo.com/group/ada_ru/join
    (Yahoo! ID required)

<*> To change settings via email:
    [email protected] 
    [email protected]

<*> To unsubscribe from this group, send an email to:
    [email protected]

<*> Your use of Yahoo Groups is subject to:
    https://info.yahoo.com/legal/us/yahoo/utos/terms/
Sergey Dukov
RE: [ada_ru] Пакеты реализаций множеств натуральны чисел на языке Ada 2012
2017-12-21 13:43:34
On 12/21/2017 12:15 PM, Dukov Sergey [email protected] [ada ru] wrote:
> 
> Отсюда вопрос, а
> работают ли инструкции расширения AVX с битовыми картами?

В расширениях инструкций от Intel всегда можно найти все мыслимые инструкции. Там правда есть
небольшая засада - первая версия очередного набора инструкций обычно для маркетологов, а вторая и
далее - уже для обычных программистов. Поэтому если что-то не хватило в AVX - поищите в AVX2. :)
[Sergey Dukov] 
Я, наверное, и имел в виду AVX2. Или какое там расширение векторных вычислений имеется в
процессорах Intel(R) Core(TM) i7.



------------------------------------

------------------------------------


------------------------------------

Yahoo Groups Links

<*> To visit your group on the web, go to:
    http://groups.yahoo.com/group/ada ru/

<*> Your email settings:
    Individual Email | Traditional

<*> To change settings online go to:
    http://groups.yahoo.com/group/ada ru/join
    (Yahoo! ID required)

<*> To change settings via email:
    ada [email protected] 
    ada [email protected]

<*> To unsubscribe from this group, send an email to:
    ada [email protected]

<*> Your use of Yahoo Groups is subject to:
    https://info.yahoo.com/legal/us/yahoo/utos/terms/
Новое сообщение:
Страницы: 1

Чтобы оставить новое сообщение необходимо Зарегистрироваться и Войти