Всем доброго времени суток. Имеется задачка поиска ближайшего значения в списке к искомому. Решить её можно так.
Код
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 написал: Как лучше всего решить это дело бинарным поиском на языке М?
Алексей, а смысл, учитывая входные данные для поиска? Думаю, что проще будет слиянием и сортировкой и сдвиговой в нужную сторону индексацией задачу решить. Да и по скорости, также полагаю, будет быстрее, чем перемещаться по индексам буферизированного списка. В общем тестировать нужно. updated Индексация - не нужна
Гениально! Завтра погоняю. Спасибо огромное, я тут полдня башку ломаю. З.Ы. Все летает! Это что-то с чем-то. Забираю в копилку. Андрей - Вы лучший.
Блин, есть косяк, нельзя прям заполнением вверх/вниз без разбора. надо для каждого значения с приоритетом 0 сравнивать два ближайших с приоритетом 1 и по модулю выбирать соответствие, но в любом случае, думаю что с этим я справлюсь, все равно должно быстрее работать.
PooHkrd написал: Блин, есть косяк, нельзя прям заполнением вверх/вниз без разбора.
Правильно. Всё зависит от того, что вы хотите получить ближайшее меньшее или равное, или ближайшее большее или равное. В моём примере сделано бессмысленное заполнение вниз для 9,7, подставлено 9,3. Но ведь по условию сортировки и приоритета ищется ближайшее большее или равное. По идее, нужно для 9,7 оставить null, как признак - нет данных.
Андрей VG, в запросе первого поста я искал ближайшее по модулю наименьшей разности. В принципе идея уже есть как решить. Изначальный столбец сместить на один элемент, List.Zip'ом соеденить с исходным списком и посчитать средние, уже вот с этим столбцом делать Combine, а дальше все тоже самое. Завтра поковыряюсь - выложу. Ещё раз огромное спасибо за идею. Скорость будет огонь.
PooHkrd написал: искал ближайшее по модулю наименьшей разности
Ну, тогда нужно сопоставлять две составляющие после сортировки заполнение вниз и заполнение вверх (в примере 1,4 и 1,9 привязались каждый ко своему ближайшему по модулю). Разность с какой будет меньше - ту и использовать. Осталось только определить, что если значение в TData ровно по середине?
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]
Вернет три значения середину, ближайшее минимальное и ближайшее максимальное. Далее можно доработать - что именно выбрать