AXForum  
Вернуться   AXForum > Microsoft Dynamics AX > DAX: Программирование
All
Забыли пароль?
Зарегистрироваться Правила Справка Пользователи Сообщения за день Поиск Все разделы прочитаны

 
 
Опции темы Поиск в этой теме Опции просмотра
Старый 23.11.2010, 00:31   #1  
gl00mie is offline
gl00mie
Участник
MCBMSS
Most Valuable Professional
Лучший по профессии 2017
Лучший по профессии 2015
Лучший по профессии 2014
Лучший по профессии AXAWARD 2013
Лучший по профессии 2011
Лучший по профессии 2009
 
3,684 / 5788 (200) ++++++++++
Регистрация: 28.11.2005
Адрес: Москва
Записей в блоге: 3
Последовательная замена множества уникальных значений на другие без возникновения дубликатов
Наверно, многим уже приходилось решать такую задачу, но я с ней столкнулся лишь недавно. В общем, на входе есть некое множество уникальных значений, допустим, {0, 1, 3, 7, 9, 15, 20}, их последовательно нужно заменить на значения из другого множества, скажем, {1, 2, 3, 4, 5, 6, 7}, но так, чтобы не нарушалась уникальность значений результирующего множества, т.е. чтобы замена ни на каком шаге не приводила к появлению дубликатов (оба множества могут частично пересекаться). Пример из жизни: замена определенным образом сгенерированных значений поля на значения, сгенерированные иным образом - при условии, что по этому полю существует уникальный индекс. По ходу дела получился нижеприведенный метод, возвращающий список с парами значений для замены в нужном порядке.
X++:
/// <summary>
///     возвращает список пар [исходное значение, новое значение] для последовательной замены исходных значений на
///     новые таким образом, чтобы на любом шаге замены в изменяемом множестве значений не возникало дубликатов
///     может использоваться, к примеру, для перебивки значений поля таблицы, на котором висит уникальный индекс
/// </summary>
/// <param name="_setOfValues2Replace">
///     множество значений, подлежащих замене
///     должно быть непустым и иметь простой значимый (не ссылочный) базовый тип
/// </param>
/// <param name="_setOfNewValues">
///     множество новых значений, на которые надо заменить исходные
///     может полностью или частично пересекаться со значениями, подлежащими замене
///     должно иметь тот же базовый тип и число элементов, что и _setOfValues2Replace
/// </param>
/// <returns>
///     список контейнеров [исходное значение, новое значение] для последовательной замены в нужном порядке
///     либо пустой список, если замена невозможна (к примеру, множества исходных и новых значений тождественны)
/// </returns>
/// <remarks>
///     ACHTUNG!!! исходные множества изменяются!
/// </remarks>
/// <exception cref="Exception::Error">
///     выбрасывается, если входные параметры не соответствуют предусловиям
/// </exception>
public static client server List DEV_getListOfValueReplacementPairs(Set _setOfValues2Replace, Set _setOfNewValues)
{
    Set         setOfUniqueNewValues;
    Set         setOfCommonValues;
    SetIterator setIterNew;
    SetIterator setIterOld;
    anytype     oldValue;
    anytype     newValue;
    Types       baseType;
    Counter     nElements;
    List        ret;
    ;
    if (_setOfValues2Replace)
    {
        baseType    = _setOfValues2Replace.typeId();
        nElements   = _setOfValues2Replace.elements();
    }
    // проверка предусловий
    if (!(      _setOfNewValues
        &&      _setOfValues2Replace
        &&      nElements   >  0
        &&      nElements   == _setOfNewValues.elements()
        &&      baseType    == _setOfNewValues.typeId()
        &&  (   baseType    == Types::Date
            ||  baseType    == Types::Enum
            ||  baseType    == Types::Guid
            ||  baseType    == Types::Int64
            ||  baseType    == Types::Integer
            ||  baseType    == Types::Real
            ||  baseType    == Types::RString
            ||  baseType    == Types::String
            ||  baseType    == Types::Time
            ||  baseType    == Types::UtcDateTime
            ||  baseType    == Types::VarString
            )
       ))
    {
        throw error( Error::wrongUseOfFunction( funcname() ) );
    }
    ret = new List( Types::Container );
    setOfCommonValues = Set::intersection( _setOfValues2Replace, _setOfNewValues );
    if (setOfCommonValues.elements() < nElements)
    {
        if (!setOfCommonValues.empty())
        {
            setOfUniqueNewValues = Set::difference( _setOfNewValues, setOfCommonValues );
            setIterNew = new SetIterator( setOfUniqueNewValues );
            setIterOld = new SetIterator( setOfCommonValues );
            while (setIterNew.more())
            {
                if (!setIterOld.more())
                {
                    break;
                }
                oldValue = setIterOld.value();
                newValue = setIterNew.value();
                ret.addEnd( [ oldValue, newValue ] );
                _setOfNewValues.remove( newValue );
                _setOfValues2Replace.remove( oldValue );
                setOfUniqueNewValues.remove( newValue );
                if (_setOfNewValues.in( oldValue ))
                {
                    setOfUniqueNewValues.add( oldValue );
                    setIterNew.begin();
                }
                else
                {
                    setIterNew.next();
                }
                setIterOld.next();
            }
            Debug::assert( _setOfValues2Replace.elements() == setOfUniqueNewValues.elements() );
        }
        else
        {
            setIterNew = new SetIterator( _setOfNewValues );
        }
        // оставшиеся на замену значения никак не пересекаются с новыми
        setIterNew.begin();
        setIterOld = new SetIterator( _setOfValues2Replace );
        while (setIterNew.more() && setIterOld.more())
        {
            oldValue = setIterOld.value();
            newValue = setIterNew.value();
            ret.addEnd( [ oldValue, newValue ] );
            setIterNew.next();
            setIterOld.next();
        }
        Debug::assert( ret.elements() == nElements );
    }
    return ret;
}

Последний раз редактировалось gl00mie; 23.11.2010 в 01:52. Причина: typo...
За это сообщение автора поблагодарили: mazzy (5), Wamr (3).
Старый 23.11.2010, 00:43   #2  
mazzy is offline
mazzy
Участник
Аватар для mazzy
Лучший по профессии 2015
Лучший по профессии 2014
Лучший по профессии AXAWARD 2013
Лучший по профессии 2011
Лучший по профессии 2009
 
29,472 / 4494 (208) ++++++++++
Регистрация: 29.11.2001
Адрес: Москва
Записей в блоге: 10
Цитата:
Сообщение от gl00mie Посмотреть сообщение
множество ... нужно заменить на ... множество ...чтобы не нарушалась уникальность значений
Заменить? Почему именно этот глагол?
создай третье множество из первых двух. И не мучайся

мне кажется, что задача то не полностью сформулирована.
1. есть множество.
2. есть функция (map), которая переводит значения из первого множества (область определения) в другие значения (облать значений).

Задача - вычислить функцию для всех значений из первого множества.

1. добавляешь новое промежуточное поле - результат функции.
2. ставишь туда новые значения.
3. далее
ttsbegin;
recordset_update ... oldField = newField;
ttscommit;
4. далее удаляешь промежуточное поле.
__________________
полезное на axForum, github, vk, coub.
За это сообщение автора поблагодарили: S.Kuskov (5).
Старый 23.11.2010, 00:46   #3  
mazzy is offline
mazzy
Участник
Аватар для mazzy
Лучший по профессии 2015
Лучший по профессии 2014
Лучший по профессии AXAWARD 2013
Лучший по профессии 2011
Лучший по профессии 2009
 
29,472 / 4494 (208) ++++++++++
Регистрация: 29.11.2001
Адрес: Москва
Записей в блоге: 10
Цитата:
Сообщение от gl00mie Посмотреть сообщение
Пример из жизни: замена определенным образом сгенерированных значений поля на значения, сгенерированные иным образом - при условии, что по этому полю существует уникальный индекс.
выключать уникальный индекс ни в какой момент нельзя?
__________________
полезное на axForum, github, vk, coub.
Старый 23.11.2010, 01:07   #4  
mazzy is offline
mazzy
Участник
Аватар для mazzy
Лучший по профессии 2015
Лучший по профессии 2014
Лучший по профессии AXAWARD 2013
Лучший по профессии 2011
Лучший по профессии 2009
 
29,472 / 4494 (208) ++++++++++
Регистрация: 29.11.2001
Адрес: Москва
Записей в блоге: 10
Цитата:
Сообщение от gl00mie Посмотреть сообщение
последовательно нужно заменить на
а почему последовательно?

в рамках одной транзакции уникальность может быть нарушена.
главное, чтобы она не нарушалась за пределами транзакции.

X++:
// test for [url=http://axforum.info/forums/showthread.php?t=35529]Последовательная замена множества уникальных значений на другие без возникновения дубликатов[/url]
static void Job13(Args _args)
{
    Table1  Table1;

    ttsbegin;
    // очистка
    delete_from Table1;

    // заполнение первоначальными значениями
    Table1.clear();   Table1.Key = "0";    Table1.NewKey = "1"; Table1.insert();
    Table1.clear();   Table1.Key = "1";    Table1.NewKey = "2"; Table1.insert();
    Table1.clear();   Table1.Key = "3";    Table1.NewKey = "3"; Table1.insert();
    Table1.clear();   Table1.Key = "7";    Table1.NewKey = "4"; Table1.insert();
    Table1.clear();   Table1.Key = "9";    Table1.NewKey = "5"; Table1.insert();
    Table1.clear();   Table1.Key = "15";   Table1.NewKey = "6"; Table1.insert();
    Table1.clear();   Table1.Key = "20";   Table1.NewKey = "7"; Table1.insert();
    ttscommit;

    // здесь можно остановиться и обозреть таблицу
    //break;

    ttsbegin;
    UPDATE_RECORDSET Table1 SETTING key = Table1.newKey;
    ttscommit;
}
Изображения
 
Вложения
Тип файла: xpo SharedProject_test.xpo (4.0 Кб, 259 просмотров)
__________________
полезное на axForum, github, vk, coub.
Старый 23.11.2010, 01:15   #5  
gl00mie is offline
gl00mie
Участник
MCBMSS
Most Valuable Professional
Лучший по профессии 2017
Лучший по профессии 2015
Лучший по профессии 2014
Лучший по профессии AXAWARD 2013
Лучший по профессии 2011
Лучший по профессии 2009
 
3,684 / 5788 (200) ++++++++++
Регистрация: 28.11.2005
Адрес: Москва
Записей в блоге: 3
Цитата:
Сообщение от mazzy Посмотреть сообщение
Заменить? Почему именно этот глагол?
Потому что он точнее всего отражает суть того, что мне нужно было сделать
Цитата:
Сообщение от mazzy Посмотреть сообщение
добавляешь новое промежуточное поле - результат функции.
Нужно было решить задачу на работающей системе; просто так менять схему данных в ней "по живому" нельзя. Кроме того, на поле в моем случае есть ссылки из других таблиц, их нужно было обновлять вместе со значением поля для сохранения консистентности данных.
Цитата:
Сообщение от mazzy Посмотреть сообщение
выключать уникальный индекс ни в какой момент нельзя?
Боже упаси! В базе ведь куча компаний, люди работают - еще нагенерят дубликатов, разгребай потом, а мне надо-то было только в паре компаний данные перебить. А караулить до ночи, когда таблица вроде как никому не нужна, очень уж не хотелось.
Старый 23.11.2010, 01:19   #6  
mazzy is offline
mazzy
Участник
Аватар для mazzy
Лучший по профессии 2015
Лучший по профессии 2014
Лучший по профессии AXAWARD 2013
Лучший по профессии 2011
Лучший по профессии 2009
 
29,472 / 4494 (208) ++++++++++
Регистрация: 29.11.2001
Адрес: Москва
Записей в блоге: 10
Цитата:
Сообщение от gl00mie Посмотреть сообщение
на входе есть некое множество уникальных значений ... последовательно нужно заменить на значения из другого множества ... но так, чтобы не нарушалась уникальность значений результирующего множества, т.е. чтобы замена ни на каком шаге не приводила к появлению дубликатов (оба множества могут частично пересекаться).
ЕСЛИ же говорить о математической постановке задачи именно с множествами (не пользуясь хаками нарушения уникальности внутри транзакции),
ТО возникает интересный вопрос - бывают ли такие множества, когда замену произвести нельзя?

Для вырожденных случаев можно легко привести пример таких множеств.
Например, множество {1, 2} нельзя последовательно заменить на множество {2, 1} с сохранением уникальности на каждом шаге.

Как должен вести себя алгоритм для таких множеств с математической точки зрения?
Как определить, что множества именно такие?
__________________
полезное на axForum, github, vk, coub.
Старый 23.11.2010, 01:22   #7  
mazzy is offline
mazzy
Участник
Аватар для mazzy
Лучший по профессии 2015
Лучший по профессии 2014
Лучший по профессии AXAWARD 2013
Лучший по профессии 2011
Лучший по профессии 2009
 
29,472 / 4494 (208) ++++++++++
Регистрация: 29.11.2001
Адрес: Москва
Записей в блоге: 10
Цитата:
Сообщение от gl00mie Посмотреть сообщение
Кроме того, на поле в моем случае есть ссылки из других таблиц, их нужно было обновлять вместе со значением поля для сохранения консистентности данных.
понятно.
тогда вместо update нужно использовать renamePrimaryKey.
главное - внутри транзакции значения могут быть и неуникальными.

Цитата:
Сообщение от gl00mie Посмотреть сообщение
А караулить до ночи, когда таблица вроде как никому не нужна, очень уж не хотелось.
Все равно на время апдейта таблица будет залочена
__________________
полезное на axForum, github, vk, coub.
Старый 23.11.2010, 01:27   #8  
gl00mie is offline
gl00mie
Участник
MCBMSS
Most Valuable Professional
Лучший по профессии 2017
Лучший по профессии 2015
Лучший по профессии 2014
Лучший по профессии AXAWARD 2013
Лучший по профессии 2011
Лучший по профессии 2009
 
3,684 / 5788 (200) ++++++++++
Регистрация: 28.11.2005
Адрес: Москва
Записей в блоге: 3
Цитата:
Сообщение от mazzy Посмотреть сообщение
Для вырожденных случаев можно легко привести пример таких множеств. Например, множество {1, 2} нельзя последовательно заменить на множество {2, 1} с сохранением уникальности на каждом шаге.
Как должен вести себя алгоритм для таких множеств с математической точки зрения? Как определить, что множества именно такие?
На счет математической стороны вопроса - не знаю У меня соответствие исходных и конечных значений не задано жестко, поэтому заменять можно произвольным образом, кроме того, обожаемые мной Set'ы в Аксапте всегда отсортированы, так что там {1, 2} и {2, 1} тождественны. Для тождественных множеств исходных и конечных значений метод возвращает пустой список - заменять ничего не нужно. К слову, щас подумал еще о том, что пары, где исходное и конечное значение совпадают, тоже не следовало бы включать в результирующий список; у меня этот случай отлавливался в другом месте.
Старый 23.11.2010, 01:37   #9  
gl00mie is offline
gl00mie
Участник
MCBMSS
Most Valuable Professional
Лучший по профессии 2017
Лучший по профессии 2015
Лучший по профессии 2014
Лучший по профессии AXAWARD 2013
Лучший по профессии 2011
Лучший по профессии 2009
 
3,684 / 5788 (200) ++++++++++
Регистрация: 28.11.2005
Адрес: Москва
Записей в блоге: 3
Цитата:
Сообщение от mazzy Посмотреть сообщение
тогда вместо update нужно использовать renamePrimaryKey.
С точки зрения Аксапты поле, значения которого я перебивал, не является первичным ключом, кроме того, оно вообще-то уникально лишь в рамках комбинации значений других полей (впрочем, как и любой первичный ключ в таблице, данные которой хранятся в разрезе компаний).
Цитата:
Сообщение от mazzy Посмотреть сообщение
главное - внутри транзакции значения могут быть и неуникальными.
При условии, что update_recordset уйдет на СУБД одним запросом.
Цитата:
Сообщение от mazzy Посмотреть сообщение
Все равно на время апдейта таблица будет залочена
Не таблица, а определенный набор записей - и то разве что в трешке, кроме того, при использовании моего способа можно обновлять данные множеством маленьких транзакций, получая после завершения каждой консистентный результат.
Старый 23.11.2010, 01:40   #10  
mazzy is offline
mazzy
Участник
Аватар для mazzy
Лучший по профессии 2015
Лучший по профессии 2014
Лучший по профессии AXAWARD 2013
Лучший по профессии 2011
Лучший по профессии 2009
 
29,472 / 4494 (208) ++++++++++
Регистрация: 29.11.2001
Адрес: Москва
Записей в блоге: 10
Цитата:
Сообщение от gl00mie Посмотреть сообщение
обожаемые мной Set'ы в Аксапте всегда отсортированы, так что там {1, 2} и {2, 1} тождественны.
М-м-м? Т.е. множества еще и упорядочены?

все равно что-то не то.
адаптировал метод класса в job'ик. плюс добавил человеческий вывод в инфолог.

задал множества {1,2} и {2,3}
получил срабатывание assert + странные результаты.
Нажмите на изображение для увеличения
Название: 1.PNG
Просмотров: 611
Размер:	83.9 Кб
ID:	6411

и все-таки: почему последовательно, а не в одной транзакции?
может все-таки добавить поле с новым значением, и тупо заменить у каждой записи?

X++:
/// <summary>
///     возвращает список пар [исходное значение, новое значение] для последовательной замены исходных значений на
///     новые таким образом, чтобы на любом шаге замены в изменяемом множестве значений не возникало дубликатов
///     может использоваться, к примеру, для перебивки значений поля таблицы, на котором висит уникальный индекс
/// </summary>
/// <param name="_setOfValues2Replace">
///     множество значений, подлежащих замене
///     должно быть непустым и иметь простой значимый (не ссылочный) базовый тип
/// </param>
/// <param name="_setOfNewValues">
///     множество новых значений, на которые надо заменить исходные
///     может полностью или частично пересекаться со значениями, подлежащими замене
///     должно иметь тот же базовый тип и число элементов, что и _setOfValues2Replace
/// </param>
/// <returns>
///     список контейнеров [исходное значение, новое значение] для последовательной замены в нужном порядке
///     либо пустой список, если замена невозможна (к примеру, множества исходных и новых значений тождественны)
/// </returns>
/// <remarks>
///     ACHTUNG!!! исходные множества изменяются!
/// </remarks>
/// <exception cref="Exception::Error">
///     выбрасывается, если входные параметры не соответствуют предусловиям
/// </exception>
static void DEV_getListOfValueReplacementPairs(Args args)
{
    Set _setOfValues2Replace = new Set(Types::Integer);
    Set _setOfNewValues = new Set(Types::Integer);

    Set         setOfUniqueNewValues;
    Set         setOfCommonValues;
    SetIterator setIterNew;
    SetIterator setIterOld;
    anytype     oldValue;
    anytype     newValue;
    Types       baseType;
    Counter     nElements;
    List        ret;
    ;
    //////////////////
    /**/
    _setOfValues2Replace.add(1);      _setOfNewValues.add(2);
    _setOfValues2Replace.add(2);      _setOfNewValues.add(1);
    /*
    _setOfValues2Replace.add(0);      _setOfNewValues.add(1);
    _setOfValues2Replace.add(1);      _setOfNewValues.add(2);
    _setOfValues2Replace.add(3);      _setOfNewValues.add(3);
    _setOfValues2Replace.add(7);      _setOfNewValues.add(4);
    _setOfValues2Replace.add(9);      _setOfNewValues.add(5);
    _setOfValues2Replace.add(15);     _setOfNewValues.add(6);
    _setOfValues2Replace.add(20);     _setOfNewValues.add(7);
    */

    //////////////////

    if (_setOfValues2Replace)
    {
        baseType    = _setOfValues2Replace.typeId();
        nElements   = _setOfValues2Replace.elements();
    }
    // проверка предусловий
    if (!(      _setOfNewValues
        &&      _setOfValues2Replace
        &&      nElements   >  0
        &&      nElements   == _setOfNewValues.elements()
        &&      baseType    == _setOfNewValues.typeId()
        &&  (   baseType    == Types::Date
            ||  baseType    == Types::Enum
            ||  baseType    == Types::Guid
            ||  baseType    == Types::Int64
            ||  baseType    == Types::Integer
            ||  baseType    == Types::Real
            ||  baseType    == Types::RString
            ||  baseType    == Types::String
            ||  baseType    == Types::Time
            ||  baseType    == Types::UtcDateTime
            ||  baseType    == Types::VarString
            )
       ))
    {
        throw error( Error::wrongUseOfFunction( funcname() ) );
    }
    ret = new List( Types::Container );
    setOfCommonValues = Set::intersection( _setOfValues2Replace, _setOfNewValues );
    if (setOfCommonValues.elements() < nElements)
    {
        if (!setOfCommonValues.empty())
        {
            setOfUniqueNewValues = Set::difference( _setOfNewValues, setOfCommonValues );
            setIterNew = new SetIterator( setOfUniqueNewValues );
            setIterOld = new SetIterator( setOfCommonValues );
            while (setIterNew.more())
            {
                if (!setIterOld.more())
                {
                    break;
                }
                oldValue = setIterOld.value();
                newValue = setIterNew.value();
                ret.addEnd( [ oldValue, newValue ] );
                _setOfNewValues.remove( newValue );
                _setOfValues2Replace.remove( oldValue );
                setOfUniqueNewValues.remove( newValue );
                if (_setOfNewValues.in( oldValue ))
                {
                    setOfUniqueNewValues.add( oldValue );
                    setIterNew.begin();
                }
                else
                {
                    setIterNew.next();
                }
                setIterOld.next();
            }
            Debug::assert( _setOfValues2Replace.elements() == setOfUniqueNewValues.elements() );
        }
        else
        {
            setIterNew = new SetIterator( _setOfNewValues );
        }
        // оставшиеся на замену значения никак не пересекаются с новыми
        setIterNew.begin();
        setIterOld = new SetIterator( _setOfValues2Replace );
        while (setIterNew.more() && setIterOld.more())
        {
            oldValue = setIterOld.value();
            newValue = setIterNew.value();
            ret.addEnd( [ oldValue, newValue ] );
            setIterNew.next();
            setIterOld.next();
        }
        Debug::assert( ret.elements() == nElements );
    }

    info(ret.definitionString());
    info(ret.xml());
}
__________________
полезное на axForum, github, vk, coub.

Последний раз редактировалось mazzy; 23.11.2010 в 02:06. Причина: поправил код согласно исправлениям gl00mie
Старый 23.11.2010, 01:44   #11  
mazzy is offline
mazzy
Участник
Аватар для mazzy
Лучший по профессии 2015
Лучший по профессии 2014
Лучший по профессии AXAWARD 2013
Лучший по профессии 2011
Лучший по профессии 2009
 
29,472 / 4494 (208) ++++++++++
Регистрация: 29.11.2001
Адрес: Москва
Записей в блоге: 10
Цитата:
Сообщение от gl00mie Посмотреть сообщение
кроме того, при использовании моего способа можно обновлять данные множеством маленьких транзакций, получая после завершения каждой консистентный результат.
разве что так.
но:
1. set для большого числа записей будет работать очень-очень-очень медленно, да еще и с квадратичным временем O(n^2).
2. все равно нужно будет делать в одной транзакции - ведь важно, чтобы при работе алгоритма не появлялись новые записи с кодами, о которых алгоритм не знает

может таки одна транзакция лучше?
__________________
полезное на axForum, github, vk, coub.
Старый 23.11.2010, 01:59   #12  
gl00mie is offline
gl00mie
Участник
MCBMSS
Most Valuable Professional
Лучший по профессии 2017
Лучший по профессии 2015
Лучший по профессии 2014
Лучший по профессии AXAWARD 2013
Лучший по профессии 2011
Лучший по профессии 2009
 
3,684 / 5788 (200) ++++++++++
Регистрация: 28.11.2005
Адрес: Москва
Записей в блоге: 3
Цитата:
Сообщение от mazzy Посмотреть сообщение
задал множества {1,2} и {2,3}, получил срабатывание assert + странные результаты.
Пардон, когда переносил код с рабочего приложения для "приукрашивания" комментариями и проч., забыл перенести последнюю версию, в которой не был пропущен вызов setIterOld.next() внутри первого цикла - извечные проблемы с итераторами Поправил код в исходном сообщении. Собственно, можно было бы использовать в данном случае SetEnumerator, но решил оставить итератор для единообразия кода...
Старый 23.11.2010, 02:14   #13  
gl00mie is offline
gl00mie
Участник
MCBMSS
Most Valuable Professional
Лучший по профессии 2017
Лучший по профессии 2015
Лучший по профессии 2014
Лучший по профессии AXAWARD 2013
Лучший по профессии 2011
Лучший по профессии 2009
 
3,684 / 5788 (200) ++++++++++
Регистрация: 28.11.2005
Адрес: Москва
Записей в блоге: 3
Цитата:
Сообщение от mazzy Посмотреть сообщение
set для большого числа записей будет работать очень-очень-очень медленно, да еще и с квадратичным временем O(n^2).
С чего бы это? Я лично всегда был уверен, что Set'ы и Map'ы за счет сортировки используют бинарный поиск, и зависимость времени поиска - O(log2(n)+1).
Старый 23.11.2010, 02:26   #14  
mazzy is offline
mazzy
Участник
Аватар для mazzy
Лучший по профессии 2015
Лучший по профессии 2014
Лучший по профессии AXAWARD 2013
Лучший по профессии 2011
Лучший по профессии 2009
 
29,472 / 4494 (208) ++++++++++
Регистрация: 29.11.2001
Адрес: Москва
Записей в блоге: 10
Цитата:
Сообщение от gl00mie Посмотреть сообщение
извечные проблемы с итераторами
если честно, то очень хочется использовать рекурсию.
но рекурсия - слишком расточительное удовольствие.

может изменить постановку? может не нужно списка, а достаточно всего лишь одной пары?
Тогда
1. в метод передаются два множества.
2. метод возвращает одну пару для замены (или пустое значение)
3. метод (или вызывающий код) убирает полученную пару из множеств
4. снова вызвать метод

тогда на псевдокоде это будет выглядеть так
X++:
[oldKey, newKey] getPair(oldSet, NewSet)
{
    if( oldSet.empty() )
        return []; // нечего менять - поэтому ничего менять не нужно 

    if( newSet.empty() )
        return []; // не на что менять - поэтому ничего менять не нужно 

    seedSet = Set::difference( newSet, oldSet ); // зародыши: новые значения будут браться отсюда
    if( seedSet.empty() )
        return []; // нет новых значений (уже использованы или множества совпадают) - ничего менять не нужно 

    deadSet = Set::difference( oldSet, newSet ); // мертвенькие: они исчезнут
    if( deadSet.empty() )
        return []; // все старые значения уже есть в новых (или множества совпадают) - ничего менять не нужно 

    newKey = seedSet.anyValue(); // любое значение из множества зародышей
    oldKey = deadSet.anyValue(); // любое значение из множества мертвеньких
    return [oldKey, newKey];
}

pair = getPair( oldSet, newSet );
while( pair != [] )
{
    [oldKey, newKey] = pair;
    // do something with oldKey, newKey

    // next iteration
    oldSet.remove(oldKey);
    newSet.remove(newKey);
    pair = getPair( oldSet, newSet );
}
другими словами:
а) если множество старых и множество новых совпадают, то ничего менять не нужно
б) стараемся совпадающее не трогать (чтобы уменьшить число операций с базой)

как-то так.
главное - по ходу множества уменьшаются. Типа псевдорекурсия. И никаких итераторов

в качестве дальнейшей оптимизации можно подумать о совмещении difference+anyValue.
Но не уверен, что реализованный на X++ метод difference получится быстрее, чем в ядре.

============
Спасибо за интересную задачу.
У меня RU6 поставился. Пойду спать
__________________
полезное на axForum, github, vk, coub.
Старый 23.11.2010, 02:32   #15  
mazzy is offline
mazzy
Участник
Аватар для mazzy
Лучший по профессии 2015
Лучший по профессии 2014
Лучший по профессии AXAWARD 2013
Лучший по профессии 2011
Лучший по профессии 2009
 
29,472 / 4494 (208) ++++++++++
Регистрация: 29.11.2001
Адрес: Москва
Записей в блоге: 10
Цитата:
Сообщение от gl00mie Посмотреть сообщение
С чего бы это? Я лично всегда был уверен, что Set'ы и Map'ы за счет сортировки используют бинарный поиск, и зависимость времени поиска - O(log2(n)+1).
1. не уверен
2. внутри есть цикл, в котором вызывается difference. Даже если сам difference работает O(log2(n)+1), то вся конструкция будет O(n*(log2(n)+1)). А скорее O(n^2) из-за intersection.

Тут конечно считать нужно... Но intersection + difference внутри цикла сильно смущают. Особенно на больших множествах

еще раз спасибо за клевую задачу.
__________________
полезное на axForum, github, vk, coub.
Старый 23.11.2010, 08:20   #16  
gl00mie is offline
gl00mie
Участник
MCBMSS
Most Valuable Professional
Лучший по профессии 2017
Лучший по профессии 2015
Лучший по профессии 2014
Лучший по профессии AXAWARD 2013
Лучший по профессии 2011
Лучший по профессии 2009
 
3,684 / 5788 (200) ++++++++++
Регистрация: 28.11.2005
Адрес: Москва
Записей в блоге: 3
Какой там внутри цикла?! Они внутри 2-х if!
Старый 23.11.2010, 09:08   #17  
mazzy is offline
mazzy
Участник
Аватар для mazzy
Лучший по профессии 2015
Лучший по профессии 2014
Лучший по профессии AXAWARD 2013
Лучший по профессии 2011
Лучший по профессии 2009
 
29,472 / 4494 (208) ++++++++++
Регистрация: 29.11.2001
Адрес: Москва
Записей в блоге: 10
Цитата:
Сообщение от gl00mie Посмотреть сообщение
Какой там внутри цикла?! Они внутри 2-х if!
Точно! Вчера спросонья ошипся.

Значит, и в моем алгоритме можно вынести оба difference за цикл.
вот и получается структурная разница - у тебя intersection + difference, а у меня difference + difference.

вот мой исправленный алгоритм без итераторов на псевдокоде:
(плюс, в качестве побочного эффекта, исходные множества oldSet, newSet остаются не изменными. т.е. удалось избавиться от побочных эффектов в передаваемых в алгоритм параметрах )
X++:
[oldKey, newKey] getPair(deadSet, seedSet)
{
    if( deadSet.empty() )
        return []; // нечего менять - поэтому ничего менять не нужно 

    if( seedSet.empty() )
        return []; // не на что менять - поэтому ничего менять не нужно 

    newKey = seedSet.anyValue(); // любое значение из множества зародышей
    oldKey = deadSet.anyValue(); // любое значение из множества мертвеньких
    return [oldKey, newKey];
}

seedSet = Set::difference( newSet, oldSet ); // зародыши: новые значения будут браться отсюда
deadSet = Set::difference( oldSet, newSet ); // мертвенькие: они исчезнут
pair = getPair( deadSet, seedSet );
while( pair != [] )
{
    [oldKey, newKey] = pair;
    // do something with oldKey, newKey

    // next iteration
    deadSet.remove(oldKey);
    seedSet.remove(newKey);
    pair = getPair( deadSet, seedSet );
}
__________________
полезное на axForum, github, vk, coub.
За это сообщение автора поблагодарили: gl00mie (5).
Старый 23.11.2010, 09:31   #18  
AndyD is offline
AndyD
Участник
КОРУС Консалтинг
Лучший по профессии 2015
Лучший по профессии 2014
Лучший по профессии AXAWARD 2013
Лучший по профессии 2011
 
2,560 / 2476 (88) +++++++++
Регистрация: 20.08.2005
Сергей, достаточно просто пробежать по полученным множествам
X++:
{
...
    set1 = Set::difference(_setOfValues2Replace, _setOfNewValues);
    set2 = Set::difference(_setOfNewValues, _setOfValues2Replace);
    sEnum1 = set1.getEnumerator();
    sEnum2 = set2.getEnumerator();
    while (sEnum.moveNext())
    {
        if (sEnum1.moveNext())
            ret.addEnd([sEnum.current(), sEnum1.current()]);
    }
    return ret;
}
Для множеств из примера, у gl00mie получается такая замена
1->2, 3->1, 7->3, 0->4, 9->5, 15->6, 20->7
Для такой замены
0->2, 9->4, 15->5, 20->6
__________________
Axapta v.3.0 sp5 kr2
За это сообщение автора поблагодарили: mazzy (2), gl00mie (5).
Старый 23.11.2010, 09:39   #19  
mazzy is offline
mazzy
Участник
Аватар для mazzy
Лучший по профессии 2015
Лучший по профессии 2014
Лучший по профессии AXAWARD 2013
Лучший по профессии 2011
Лучший по профессии 2009
 
29,472 / 4494 (208) ++++++++++
Регистрация: 29.11.2001
Адрес: Москва
Записей в блоге: 10
Цитата:
Сообщение от AndyD Посмотреть сообщение
Сергей, достаточно просто пробежать по полученным множествам
или так

я предполагал, что еще можно выполнить следующую оптимизацию: минимизировать число замен (число операций с БД).

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

но взглянув на это дело с утра (и после подсказки gl00mie о том, что difference - за циклом),
понял, что минимизировать нечего - все мертвенькие значения из deadSet так или иначе должны быть заменены.

поэтому соглашусь - цикл проще.
__________________
полезное на axForum, github, vk, coub.
Старый 23.11.2010, 09:43   #20  
AndyD is offline
AndyD
Участник
КОРУС Консалтинг
Лучший по профессии 2015
Лучший по профессии 2014
Лучший по профессии AXAWARD 2013
Лучший по профессии 2011
 
2,560 / 2476 (88) +++++++++
Регистрация: 20.08.2005
Я свое сообщение начал писать до того, как увидел твое - потом переделал по ходу дела
__________________
Axapta v.3.0 sp5 kr2
Теги
законченный пример, уникальность

 

Похожие темы
Тема Автор Раздел Ответов Посл. сообщение
Универсальный изменятель значений полей wojzeh DAX: Программирование 17 26.09.2013 17:47
Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Быстрый переход

Рейтинг@Mail.ru
Часовой пояс GMT +3, время: 14:31.
Powered by vBulletin® v3.8.5. Перевод: zCarot
Контактная информация, Реклама.