Последовательная замена множества уникальных значений на другие без возникновения дубликатов

[gl00mie]

Наверно, многим уже приходилось решать такую задачу, но я с ней столкнулся лишь недавно. В общем, на входе есть некое множество уникальных значений, допустим, {0, 1, 3, 7, 9, 15, 20}, их последовательно нужно заменить на значения из другого множества, скажем, {1, 2, 3, 4, 5, 6, 7}, но так, чтобы не нарушалась уникальность значений результирующего множества, т.е. чтобы замена ни на каком шаге не приводила к появлению дубликатов (оба множества могут частично пересекаться). Пример из жизни: замена определенным образом сгенерированных значений поля на значения, сгенерированные иным образом - при условии, что по этому полю существует уникальный индекс. По ходу дела получился нижеприведенный метод, возвращающий список с парами значений для замены в нужном порядке.

/// <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;
}

[mazzy]

Цитата:

Сообщение от gl00mie

множество ... нужно заменить на ... множество ...чтобы не нарушалась уникальность значений

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

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

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

1. добавляешь новое промежуточное поле - результат функции.
2. ставишь туда новые значения.
3. далее
ttsbegin;
recordset_update ... oldField = newField;
ttscommit;
4. далее удаляешь промежуточное поле.

[mazzy]

Цитата:

Сообщение от gl00mie

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

выключать уникальный индекс ни в какой момент нельзя?

[mazzy]

Цитата:

Сообщение от gl00mie

последовательно нужно заменить на

а почему последовательно?

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

// 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;
}

[gl00mie]

Цитата:

Сообщение от mazzy

Заменить? Почему именно этот глагол?

Потому что он точнее всего отражает суть того, что мне нужно было сделать

Цитата:

Сообщение от mazzy

добавляешь новое промежуточное поле - результат функции.

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

Цитата:

Сообщение от mazzy

выключать уникальный индекс ни в какой момент нельзя?

Боже упаси! В базе ведь куча компаний, люди работают - еще нагенерят дубликатов, разгребай потом, а мне надо-то было только в паре компаний данные перебить. А караулить до ночи, когда таблица вроде как никому не нужна, очень уж не хотелось.

[mazzy]

Цитата:

Сообщение от gl00mie

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

ЕСЛИ же говорить о математической постановке задачи именно с множествами (не пользуясь хаками нарушения уникальности внутри транзакции),
ТО возникает интересный вопрос - бывают ли такие множества, когда замену произвести нельзя?

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

Как должен вести себя алгоритм для таких множеств с математической точки зрения?
Как определить, что множества именно такие?

[mazzy]

Цитата:

Сообщение от gl00mie

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

понятно.
тогда вместо update нужно использовать renamePrimaryKey.
главное - внутри транзакции значения могут быть и неуникальными.

Цитата:

Сообщение от gl00mie

А караулить до ночи, когда таблица вроде как никому не нужна, очень уж не хотелось.

Все равно на время апдейта таблица будет залочена

[gl00mie]

Цитата:

Сообщение от mazzy

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

На счет математической стороны вопроса - не знаю У меня соответствие исходных и конечных значений не задано жестко, поэтому заменять можно произвольным образом, кроме того, обожаемые мной Set'ы в Аксапте всегда отсортированы, так что там {1, 2} и {2, 1} тождественны. Для тождественных множеств исходных и конечных значений метод возвращает пустой список - заменять ничего не нужно. К слову, щас подумал еще о том, что пары, где исходное и конечное значение совпадают, тоже не следовало бы включать в результирующий список; у меня этот случай отлавливался в другом месте.

[gl00mie]

Цитата:

Сообщение от mazzy

тогда вместо update нужно использовать renamePrimaryKey.

С точки зрения Аксапты поле, значения которого я перебивал, не является первичным ключом, кроме того, оно вообще-то уникально лишь в рамках комбинации значений других полей (впрочем, как и любой первичный ключ в таблице, данные которой хранятся в разрезе компаний).

Цитата:

Сообщение от mazzy

главное - внутри транзакции значения могут быть и неуникальными.

При условии, что update_recordset уйдет на СУБД одним запросом.

Цитата:

Сообщение от mazzy

Все равно на время апдейта таблица будет залочена

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

[mazzy]

Цитата:

Сообщение от gl00mie

обожаемые мной Set'ы в Аксапте всегда отсортированы, так что там {1, 2} и {2, 1} тождественны.

М-м-м? Т.е. множества еще и упорядочены?

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

задал множества {1,2} и {2,3}
получил срабатывание assert + странные результаты.


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

/// <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());
}

[mazzy]

Цитата:

Сообщение от gl00mie

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

разве что так.
но:
1. set для большого числа записей будет работать очень-очень-очень медленно, да еще и с квадратичным временем O(n^2).
2. все равно нужно будет делать в одной транзакции - ведь важно, чтобы при работе алгоритма не появлялись новые записи с кодами, о которых алгоритм не знает

может таки одна транзакция лучше?

[gl00mie]

Цитата:

Сообщение от mazzy

задал множества {1,2} и {2,3}, получил срабатывание assert + странные результаты.

Пардон, когда переносил код с рабочего приложения для "приукрашивания" комментариями и проч., забыл перенести последнюю версию, в которой не был пропущен вызов setIterOld.next() внутри первого цикла - извечные проблемы с итераторами Поправил код в исходном сообщении. Собственно, можно было бы использовать в данном случае SetEnumerator, но решил оставить итератор для единообразия кода...

[gl00mie]

Цитата:

Сообщение от mazzy

set для большого числа записей будет работать очень-очень-очень медленно, да еще и с квадратичным временем O(n^2).

С чего бы это? Я лично всегда был уверен, что Set'ы и Map'ы за счет сортировки используют бинарный поиск, и зависимость времени поиска - O(log2(n)+1).

[mazzy]

Цитата:

Сообщение от gl00mie

извечные проблемы с итераторами

если честно, то очень хочется использовать рекурсию.
но рекурсия - слишком расточительное удовольствие.

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

тогда на псевдокоде это будет выглядеть так

[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 поставился. Пойду спать

[mazzy]

Цитата:

Сообщение от 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 внутри цикла сильно смущают. Особенно на больших множествах

еще раз спасибо за клевую задачу.

[gl00mie]

Какой там внутри цикла?! Они внутри 2-х if!

[mazzy]

Цитата:

Сообщение от gl00mie

Какой там внутри цикла?! Они внутри 2-х if!

Точно! Вчера спросонья ошипся.

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

вот мой исправленный алгоритм без итераторов на псевдокоде:
(плюс, в качестве побочного эффекта, исходные множества oldSet, newSet остаются не изменными. т.е. удалось избавиться от побочных эффектов в передаваемых в алгоритм параметрах )

[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 );
}

[AndyD]

Сергей, достаточно просто пробежать по полученным множествам

{
...
    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

[mazzy]

Цитата:

Сообщение от AndyD

Сергей, достаточно просто пробежать по полученным множествам

или так

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

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

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

поэтому соглашусь - цикл проще.

[AndyD]

Я свое сообщение начал писать до того, как увидел твое - потом переделал по ходу дела