Страницы: 1
RSS
Power Query. Бинарный поиск., Как реализовать в коде максимально эффективно.
 
Всем доброго времени суток.
Имеется задачка поиска ближайшего значения в списке к искомому. Решить её можно так.
Код
let
    Список = {4.7, 1.1, 7.8, 2.3, 3.2, 4.5, 6.6},
    ЧтоИщемВСписке = 10.2,
    Поиск = let мод = List.Buffer(List.Transform( Список, (x)=> Number.Abs( x - ЧтоИщемВСписке ) ) ) in Список{ List.PositionOf( мод, List.Min( мод ) ) }
in
    Поиск

Как лучше всего решить это дело бинарным поиском на языке М? Хочу погонять на большом массиве оно быстрее будет или нет. Если у кого есть наработки буду рад увидеть.
Изменено: PooHkrd - 26.06.2019 18:34:59
Вот горшок пустой, он предмет простой...
 
Доброе время суток.
Цитата
PooHkrd написал:
Как лучше всего решить это дело бинарным поиском на языке М?
Алексей, а смысл, учитывая входные данные для поиска? Думаю, что проще будет слиянием и сортировкой и сдвиговой в нужную сторону индексацией задачу решить. Да и по скорости, также полагаю, будет быстрее, чем перемещаться по индексам буферизированного списка. В общем тестировать нужно.
updated
Индексация - не нужна :)
Изменено: Андрей VG - 26.06.2019 20:11:52
 
Цитата
Андрей VG написал:
Думаю, что проще будет слиянием и сортировкой и сдвиговой в нужную сторону индексацией задачу решить.
О, это как?  :idea: Может вы что-то такое здесь и показывали, но по таким терминам не очень понял. Можете без кода просто на пальцах алгоритм расписать?
Вот горшок пустой, он предмет простой...
 
Цитата
PooHkrd написал:
Можете без кода
Увы, уже сделал :(  Не выбрасывать же ;)
 
8-0 Гениально!  :idea:
Завтра погоняю. Спасибо огромное, я тут полдня башку ломаю.
З.Ы. Все летает! Это что-то с чем-то. Забираю в копилку. Андрей - Вы лучший.

Блин, есть косяк, нельзя прям заполнением вверх/вниз без разбора. надо для каждого значения с приоритетом 0 сравнивать два ближайших с приоритетом 1 и по модулю выбирать соответствие, но в любом случае, думаю что с этим я справлюсь, все равно должно быстрее работать.
Изменено: PooHkrd - 26.06.2019 21:01:22
Вот горшок пустой, он предмет простой...
 
Цитата
PooHkrd написал:
Блин, есть косяк, нельзя прям заполнением вверх/вниз без разбора.
Правильно. Всё зависит от того, что вы хотите получить ближайшее меньшее или равное, или ближайшее большее или равное. В моём примере сделано бессмысленное заполнение вниз для 9,7, подставлено 9,3. Но ведь по условию сортировки и приоритета ищется ближайшее большее или равное. По идее, нужно для 9,7 оставить null, как признак - нет данных.
 
Андрей VG, в запросе первого поста я искал ближайшее по модулю наименьшей разности.
В принципе идея уже есть как решить. Изначальный столбец сместить на один элемент, List.Zip'ом соеденить с исходным списком и посчитать средние, уже вот с этим столбцом делать Combine, а дальше все тоже самое. Завтра поковыряюсь - выложу. Ещё раз огромное спасибо за идею. Скорость будет огонь.
Вот горшок пустой, он предмет простой...
 
Цитата
PooHkrd написал:
искал ближайшее по модулю наименьшей разности
Ну, тогда нужно сопоставлять две составляющие после сортировки заполнение вниз и заполнение вверх (в примере 1,4 и 1,9 привязались каждый ко своему ближайшему по модулю). Разность с какой будет меньше - ту и использовать. Осталось только определить, что если значение в TData ровно по середине? ;)
 
Андрей VG,  снова спасибо!
Вот горшок пустой, он предмет простой...
 
Отлично! :)
F1 творит чудеса
 
Цитата
Андрей VG написал:
Осталось только определить, что если значение в TData ровно по середине?
Оставили мне самое сложное!  :D
Вот горшок пустой, он предмет простой...
 
Цитата
PooHkrd написал:
Оставили мне самое сложное!
Ну, да - над проблемой философы думали!  :)
 
Цитата
PooHkrd написал:
Как лучше всего решить это дело бинарным поиском на языке М? Хочу погонять на большом массиве оно быстрее будет или нет. Если у кого есть наработки буду рад увидеть.
Не знаю такой вариант считается решением.
Код
(value as any, list as list) =>
let
    valuePQ = Text.From(value,"en-us"),
    sortedList = List.Sort(list,Order.Ascending),
    itemListToText= List.Transform(sortedList, each Text.From(_, "en-us")),
    listToText = Text.From(Text.Combine(itemListToText, ",")),
    source = Web.Page(
        "<script>
            var valueText = '"& valuePQ &"';
            var value = parseFloat(valueText);
            var listText = '"& listToText &"';
            var list = listText.split(',');
            var first  = 0;
            var last = list.length -1;
            var position = -1;
            var found = false;
            var middle;
            while (found === false && first <= last){
                    middle = Math.floor((first + last)/2);
                    if (list[middle] == value){
                        found = true;
                        position = middle;
                    } else if (list[middle] > value){
                        last = middle -1;
                    } else {
                        first = middle + 1
                    }
            }
            document.write(list[middle-1] + ';' + list[middle] + ';' + list[middle+1])
        </script>"),
    resultString = source[Data]{0}[Children]{0}{1}[Children][Text]{0},
    resultList = List.RemoveItems(Text.Split(resultString,";"),{"undefined"}),
    resultDifference = List.Transform(resultList, each Number.Abs(Number.FromText(_, "en-us") - value)),
    resultPositionListMin = List.PositionOf(resultDifference, List.Min(resultDifference),Occurrence.All) 
in
    "Результат в метаданных. Вызовите функцию Value.Metadata" meta [string =  resultString , list = resultList, difference = resultDifference, positionWithMinDiff = resultPositionListMin]


Вернет три значения середину, ближайшее минимальное и ближайшее максимальное. Далее можно доработать - что именно выбрать

 
Цитата
DrillPipe написал:
такой вариант считается решением.
В первом приближении - да. Спасибо. Но, можно же и средствами Power Query сделать бинарный поиск - особых проблем нет.
Страницы: 1
Наверх