Алгоритм агрегирования пар ключ-значение, где ключи содержат числа - PullRequest
Новая
       24

Алгоритм агрегирования пар ключ-значение, где ключи содержат числа

2 голосов
/ 24 апреля 2019

Я сделаю все возможное, чтобы дать полное определение проблемы.Чтобы проиллюстрировать проблему, я приведу пример позже в моем вопросе.Возможно, вы захотите сначала перейти к примеру и прочитать мое определение проблемы позже.

Проблема

У меня есть карта, представляющая пары ключ-значение.Ключи могут заканчиваться -NUMBER, где NUMBER - целое число.Однако могут также присутствовать клавиши, не заканчивающиеся тире и цифрой.

Клавиша перед начальным -NUMBER также может содержать тире.

Может быть несколько клавиш, начинающихся ста же строка и заканчивается разными номерами.

Также может быть несколько клавиш, начинающихся с разных строк и заканчивающихся цифрами.

Общие условия

  1. Все ключи уникальны
  2. Карта не упорядочена
  3. Порядок ключей случайный
  4. Можно с уверенностью предположить, что все строки в ключах являются верхнимиcase
  5. Если есть ключ, заканчивающийся тире и цифрой n больше , гарантируется, что все ключи начинаются с одной строки и заканчиваются всеми цифрами *На карте присутствуют 1034 * с 1 <<code>m <<code>n.
  6. Не имеет значения, остаются ли оригинальные ключи, заканчивающиеся цифрами, в конечном наборе или нет

Фокус на решение

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

Пример

Ввод: 

{
    "FIRST-KEY"   = "FOO",
    "SECOND-KEY-3"= "BAZ",
    "THIRD-KEY-2" = "BAR",
    "SECOND-KEY-1"= "FOO",
    "SECOND-KEY-2"= "BAR",
    "THIRD-KEY-1" = "FOO"
}

Ожидаемый результат: 

{
    "FIRST-KEY" = "FOO",
    "SECOND-KEY"= ["FOO", "BAR", "BAZ"],
    "THIRD-KEY" = ["FOO", "BAR"]
}

или (если исходные ключи остаются в результате): 

{
    "FIRST-KEY"   = "FOO",
    "SECOND-KEY-3"= "BAZ",
    "THIRD-KEY-2" = "BAR",
    "SECOND-KEY-1"= "FOO",
    "SECOND-KEY-2"= "BAR",
    "THIRD-KEY-1" = "FOO",
    "FIRST-KEY"   = "FOO",
    "SECOND-KEY"  = ["FOO", "BAR", "BAZ"],
    "THIRD-KEY"   = ["FOO", "BAR"]
}

Заключительные примечания

Мое решение должнобыть реализован в ColdFusion.Входные данные, на которые я должен ссылаться как на карту в начале моего вопроса, называются struct в ColdFusion land.

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

Ответы [ 2 ]

4 голосов
/ 24 апреля 2019

Если все числа 1 ... n гарантированно присутствуют, простой подход состоит в том, чтобы просто пройти по всем именам ключей. Для каждого ключа используйте регулярное выражение для извлечения имени группы (то есть FIRST-KEY, SECOND-KEY и т. Д.) И необязательного суффикса -NUMBER . 

results = {};

for (key in structKeyArray(yourStruct)) {

   keyGroup  = reReplaceNoCase(key, "(.+)-\d+$", "\1", "ALL");
   insertAt  = reReplaceNoCase(key, "[^\d+$]", "", "ALL");
   isSequence = insertAt > 0;

   // ....

Если число> 0, установите логический флаг, указывающий, что текущий элемент является частью последовательности похожих ключей. Затем проверьте, обрабатывали ли вы текущую «группу» раньше. Если нет, инициализируйте его пустым массивом. 

    if (isSequence && !results.keyExists( keyGroup )) {
        results[ keyGroup ] = [];
    }

Наконец, сохраните текущее «значение». Если текущий элемент является частью последовательности, вставьте значение в существующий массив. (Поскольку -NUMBER является последовательным и начинается с 1, его можно использовать в качестве индекса массива, обеспечивающего вставку значений в правильном порядке.) В противном случае просто сохраните его как простое значение. 

    if (isSequence) {
        results[ keyGroup ][ insertAt ] = yourStruct[ key ];
    }
    else {
        results[ keyGroup ] = yourStruct[ key ];
    }

 } // end loop
1 голос
/ 25 мая 2019

Благодаря сообществу ColdFusion в Slack мы нашли решение, отвечающее моим требованиям: 

data = data.reduce(function(acc, k, v) {
    var lastElement = listLast(k, '-');
    if(isNumeric(lastElement)) {
        var newKey = reReplace(k, '-\d+$', '');
        // init array if not initialized yet
        if(!acc.keyExists(newKey)) acc[newKey] = [];
        acc[newKey][lastElement] = v;
    }

    // may be put into an else block. This is only in here to attach the original keys in any case
    acc[k] = v;

    return acc;
}, {});

IMO, очень компактный и элегантный. Более того, это в основном говорит само за себя и может быть интуитивно понятно.

Идея состоит в том, что вся проблема может быть сведена к одному сокращению . Для каждого элемента мы смотрим на последний «сегмент» (разделенный -) и, если он числовой, мы можем построить дополнительный массив для этого ключа.

Если кто-то не согласен или имеет лучшее решение, я был бы более чем счастлив увидеть его.

Наконец, спасибо за effords Ageax , Кредиты для решения идут в rodel30

...