Javascript: узнать даты окончания
Рассмотрим этот вложенный массив дат и имен:
var fDates = [
['2015-02-03', 'name1'],
['2015-02-04', 'nameg'],
['2015-02-04', 'name5'],
['2015-02-05', 'nameh'],
['1929-03-12', 'name4'],
['2023-07-01', 'name7'],
['2015-02-07', 'name0'],
['2015-02-08', 'nameh'],
['2015-02-15', 'namex'],
['2015-02-09', 'namew'],
['1980-12-23', 'name2'],
['2015-02-12', 'namen'],
['2015-02-13', 'named'],
]
Как я могу определить те даты, которые не соответствуют последовательности. Меня не волнует, повторяются ли даты или пропущены, мне просто нужны не по порядку. То есть, я должен вернуться:
results = [
['1929-03-12', 'name4'],
['2023-07-01', 'name7'],
['2015-02-15', 'namex'],
['1980-12-23', 'name2'],
]
('Namex' менее очевидно, но это не в общем порядке списка.)
Это, по-видимому, является разновидностью проблемы с наибольшим увеличением субпоследовательности (LIS) с предостережением о том, что в последовательности могут повторяться даты, но они никогда не должны отступать назад.
Случай использования. Я отсортировал и устарел записи, и вам нужно найти те, где даты "подозрительны" - возможно, ошибка ввода - для отметки для проверки.
NB1: Я использую прямой Javascript и НЕ структуру. (Я нахожусь в узле, но я ищу решение без пакетов, чтобы я мог понять, что происходит...)
Ответы
Ответ 1
Здесь адаптация LIS Rosetta Code для выполнения пользовательских функций getElement и compare. Мы можем уточнить функции сравнения и элемента-get, исходя из ваших конкретных потребностей.
function f(arr, getElement, compare){
function findIndex(input){
var len = input.length;
var maxSeqEndingHere = new Array(len).fill(1)
for(var i=0; i<len; i++)
for(var j=i-1;j>=0;j--)
if(compare(getElement(input, i), getElement(input, j)) && maxSeqEndingHere[j] >= maxSeqEndingHere[i])
maxSeqEndingHere[i] = maxSeqEndingHere[j]+1;
return maxSeqEndingHere;
}
function findSequence(input, result){
var maxValue = Math.max.apply(null, result);
var maxIndex = result.indexOf(Math.max.apply(Math, result));
var output = new Set();
output.add(maxIndex);
for(var i = maxIndex ; i >= 0; i--){
if(maxValue==0)break;
if(compare(getElement(input, maxIndex), getElement(input, i)) && result[i] == maxValue-1){
output.add(i);
maxValue--;
}
}
return output;
}
var result = findIndex(arr);
var final = findSequence(arr, result)
return arr.filter((e, i) => !final.has(i));
}
var fDates = [
['2015-02-03', 'name1'],
['2015-02-04', 'nameg'],
['2015-02-04', 'name5'],
['2015-02-05', 'nameh'],
['1929-03-12', 'name4'],
['2023-07-01', 'name7'],
['2015-02-07', 'name0'],
['2015-02-08', 'nameh'],
['2015-02-15', 'namex'],
['2015-02-09', 'namew'],
['1980-12-23', 'name2'],
['2015-02-12', 'namen'],
['2015-02-13', 'named'],
];
console.log(f(fDates, (arr, i) => arr[i][0], (a,b) => a >= b));
Ответ 2
Это решение пытается получить все допустимые последовательности и возвращает длинные последовательности для фильтрации частей.
Он работает путем итерации заданного массива и проверяет, могут ли значения построить последовательность. Если задано значение, то в результате частичного результата имеет действительный предшественник, массив добавляется с этим значением. Если не выполняется обратное отслеживание и поиск последовательности выполняется с действительным предшественником.
act. array
value 7 3 4 4 5 1 23 7 comment
----- ------------------------ ---------------------------
7 7 add array with single value
3 7 keep
3 add array with single value
4 7 keep
3 4 add value to array
4 7 keep
3 4 4 add value to array
5 7 keep
3 4 4 5 add value to array
1 7 keep
3 4 4 5 keep
1 add array with single value
23 7 23 add value to array
3 4 4 5 23 add value to array
1 23 add value to array
7 7 23 keep
7 7 fork above, filter for smaller or equal and add value
3 4 4 5 23 keep
3 4 4 5 7 fork above, filter for smaller or equal and add value
1 23 keep
1 7 fork above, filter for smaller or equal and add value
function longestSequences(array, getValue = v => v) {
return array
.reduce(function (sub, value) {
var single = true;
sub.forEach(function (s) {
var temp;
if (getValue(s[s.length - 1]) <= getValue(value)) {
s.push(value);
single = false;
return;
}
// backtracking
temp = s.reduceRight(function (r, v) {
if (getValue(v) <= getValue(r[0])) {
r.unshift(v);
single = false;
}
return r;
}, [value]);
if (temp.length !== 1 && !sub.some(s => s.length === temp.length && s.every((v, i) => getValue(v) === getValue(temp[i])))) {
sub.push(temp);
}
});
if (single) {
sub.push([value]);
}
return sub;
}, [])
.reduce(function (r, a) {
if (!r || r[0].length < a.length) {
return [a];
}
if (r[0].length === a.length) {
r.push(a);
}
return r;
}, undefined);
}
function notInSequence(array, getValue = v => v) {
var longest = longestSequences(array, getValue);
return array.filter((i => a => a !== longest[0][i] || !++i)(0));
}
var array = [7, 3, 4, 4, 5, 1, 23, 7, 8, 15, 9, 2, 12, 13],
fDates = [['2015-02-03', 'name1'], ['2015-02-04', 'nameg'], ['2015-02-04', 'name5'], ['2015-02-05', 'nameh'], ['1929-03-12', 'name4'], ['2023-07-01', 'name7'], ['2015-02-07', 'name0'], ['2015-02-08', 'nameh'], ['2015-02-15', 'namex'], ['2015-02-09', 'namew'], ['1980-12-23', 'name2'], ['2015-02-12', 'namen'], ['2015-02-13', 'named']],
usuallyFailingButNotHere = [['2015-01-01'], ['2014-01-01'], ['2015-01-02'], ['2014-01-02'], ['2015-01-03'], ['2014-01-03'], ['2014-01-04'], ['2015-01-04'], ['2014-01-05'], ['2014-01-06'], ['2014-01-07'], ['2014-01-08'], ['2014-01-09'], ['2014-01-10'], ['2014-01-11']],
test2 = [['1975-01-01'], ['2015-02-03'], ['2015-02-04'], ['2015-02-04'], ['2015-02-05'], ['1929-03-12'], ['2023-07-01'], ['2015-02-07'], ['2015-02-08']];
console.log(longestSequences(array));
console.log(notInSequence(array));
console.log(notInSequence(fDates, a => a[0]));
console.log(longestSequences(usuallyFailingButNotHere, a => a[0]));
console.log(notInSequence(usuallyFailingButNotHere, a => a[0]));
console.log(longestSequences(test2, a => a[0]));
console.log(notInSequence(test2, a => a[0]));
.as-console-wrapper { max-height: 100% !important; top: 0; }
Ответ 3
Это решение использует функцию reduce и сохраняет ранее принятую дату для проведения необходимых сравнений.
var fDates = [['2015-02-03', 'name1'], ['2015-02-04', 'nameg'], ['2015-02-04', 'name5'], ['2015-02-05', 'nameh'], ['1929-03-12', 'name4'], ['2023-07-01', 'name7'], ['2015-02-07', 'name0'], ['2015-02-08', 'nameh'], ['2015-02-15', 'namex'], ['2015-02-09', 'namew'], ['1980-12-23', 'name2'], ['2015-02-12', 'namen'], ['2015-02-13', 'named']],
results = fDates.reduce((acc, c, i, arr) => {
/*
* This function finds a potential valid sequence.
* Basically, will check if any next valid sequence is
* ahead from the passed controlDate.
*/
function sequenceAhead(controlDate) {
for (var j = i + 1; j < arr.length; j++) {
let [dt] = arr[j];
//The controlDate is invalid because at least a forward date is in conflict with its sequence.
if (dt > acc.previous && dt < controlDate) return true;
}
//The controlDate is valid because forward dates don't conflict with its sequence.
return false;
}
let [date] = c; //Current date in this iteration.
if (i > 0) { // If this is not the first iteration
if (date === acc.previous) return acc; // Same as previous date are skipped.
// If the current date is lesser than previous then is out of sequence.
// Or if there is at least valid sequence ahead.
if (date < acc.previous || sequenceAhead(date)) acc.results.push(c);
else acc.previous = date; // Else, this current date is in sequence.
}
else acc.previous = date; // Else, set the first date.
return acc;
}, { 'results': [] }).results;
console.log(results);
.as-console-wrapper { max-height: 100% !important; top: 0; }
Ответ 4
Все предыдущие ответы сосредоточены на JavaScript и, возможно, они не будут работать корректно. Поэтому я решил добавить новый ответ, посвященный алгоритму.
Как @Trees4theForest отметил в своем вопросе и комментариях, он ищет решение для Longest Увеличения подпоследовательности и out of order dates являются даты, которые не Longest Увеличения подпоследовательности (LIS) набора.
Я использовал этот метод, как показано ниже. В алгоритме это верно.
function longestIncreasingSequence(arr, strict) {
var index = 0,
indexWalker,
longestIncreasingSequence,
i,
il,
j;
// start by putting a reference to the first entry of the array in the sequence
indexWalker = [index];
// Then walk through the array using the following methodolgy to find the index of the final term in the longestIncreasing and
// a sequence (which may need altering later) which probably, roughly increases towards it - http://en.wikipedia.org/wiki/Longest_increasing_subsequence#Efficient_algorithms
for (i = 1, il = arr.length; i < il; i++) {
if (arr[i] < arr[indexWalker[index]]) {
// if the value is smaller than the last value referenced in the walker put it in place of the first item larger than it in the walker
for (j = 0; j <= index; j++) {
// As well as being smaller than the stored value we must either
// - be checking against the first entry
// - not be in strict mode, so equality is ok
// - be larger than the previous entry
if (arr[i] < arr[indexWalker[j]] && (!strict || !j || arr[i] > arr[indexWalker[j - 1]])) {
indexWalker[j] = i;
break;
}
}
// If the value is greater than [or equal when not in strict mode) as the last in the walker append to the walker
} else if (arr[i] > arr[indexWalker[index]] || (arr[i] === arr[indexWalker[index]] && !strict)) {
indexWalker[++index] = i;
}
}
// Create an empty array to store the sequence and write the final term in the sequence to it
longestIncreasingSequence = new Array(index + 1);
longestIncreasingSequence[index] = arr[indexWalker[index]];
// Work backwards through the provisional indexes stored in indexWalker checking for consistency
for (i = index - 1; i >= 0; i--) {
// If the index stored is smaller than the last one it valid to use its corresponding value in the sequence... so we do
if (indexWalker[i] < indexWalker[i + 1]) {
longestIncreasingSequence[i] = arr[indexWalker[i]];
// Otherwise we need to work backwards from the last entry in the sequence and find a value smaller than the last entry
// but bigger than the value at i (this must be possible because of the way we constructed the indexWalker array)
} else {
for (j = indexWalker[i + 1] - 1; j >= 0; j--) {
if ((strict && arr[j] > arr[indexWalker[i]] && arr[j] < arr[indexWalker[i + 1]]) ||
(!strict && arr[j] >= arr[indexWalker[i]] && arr[j] <= arr[indexWalker[i + 1]])) {
longestIncreasingSequence[i] = arr[j];
indexWalker[i] = j;
break;
}
}
}
}
return longestIncreasingSequence;
}
С помощью метода выше мы можем найти даты, которые не соответствуют порядку, как показано ниже:
// Finding Longest Increase Subsequence (LIS) set
var _longestIncreasingSequence = longestIncreasingSequence(fDates.map(([date]) => date));
// Out of order dates
var result = fDates.filter(([date]) => !_longestIncreasingSequence.includes(date));
Демо-версия онлайн (jsFiddle)
Ответ 5
вот простое self- объяснительное решение. надеюсь, это поможет вам.
const findOutOfSequenceDates = items => {
items = items.map(d => d);
const sequence = [], outOfsequence = [];
sequence.push(items.shift());
const last = ind => sequence[sequence.length - ind][0];
items.forEach(item => {
const current = new Date(item[0]);
if (current >= new Date(last(1))) {
sequence.push(item);
} else if (current >= new Date(last(2))) {
outOfsequence.push(sequence.pop());
sequence.push(item);
} else {
outOfsequence.push(item);
}
});
return outOfsequence;
};
var fDates = [
['2015-02-03', 'name1'],
['2015-02-04', 'nameg'],
['2015-02-04', 'name5'],
['2015-02-05', 'nameh'],
['1929-03-12', 'name4'],
['2023-07-01', 'name7'],
['2015-02-07', 'name0'],
['2015-02-08', 'nameh'],
['2015-02-15', 'namex'],
['2015-02-09', 'namew'],
['1980-12-23', 'name2'],
['2015-02-12', 'namen'],
['2015-02-13', 'named'],
];
console.log(findOutOfSequenceDates(fDates));
Ответ 6
Используйте тип даты Javascript. Сравните с этими объектами. Очень упрощенно,
date1 = new Date(fDates[i, 0])
date2 = new Date(fDates[i+1, 0])
if (date2 < date1) { // or whatever comparison you want ...
// flag / print / alert the date
}
Чтобы прояснить, это просто находит предметы не в порядке. Вы можете сделать это со строками, как указал Jaromanda X Однако вы используете фразу "выход из строя"; что бы это ни значило для вас, Date должна дать вам возможность определить и проверить ее. Например, "2023-07-01" неприемлемо, потому что он находится на расстоянии 8 лет или просто потому, что он не соответствует срокам 2015 года? Вам может потребоваться некоторое сравнение с более простым временным интервалом, например, один месяц, где ваше сравнение будет выглядеть примерно так:
if (date2-date1 > one_month)
Ответ 7
Резюме вашего вопроса Если я правильно понял ваш вопрос, вы пытаетесь идентифицировать записи массива, которые не соответствуют хронологическому порядку, основанному на значении свойства времени и даты.
Решение Преобразование строки/времени даты в метку времени UNIX (количество секунд, прошедших с 01/jan/1970 в 00:00:00)
Используя цикл, мы можем сохранить значение по сравнению с предыдущим показанием на одноранговое, если значение отрицательное, это указывает на ошибку в пропуске даты, если значение положительное, это указывает на то, что порядок действителен
При отрицательном мы можем создать массив, чтобы обозначить позицию ссылочного массива и его значения, позволяющие вернуться к исходному массиву и просмотреть данные.
Пример кода
var arrData = [
{date: '2015-02-03', value:'name1'},
{date: '2015-02-04', value:'nameg'},
{date: '2015-02-04', value:'name5'},
{date: '2015-02-05', value:'nameh'},
{date: '1929-03-12', value:'name4'},
{date: '2023-07-01', value:'name7'},
{date: '2015-02-07', value:'name0'},
{date: '2015-02-08', value:'nameh'},
{date: '2015-02-15', value:'namex'},
{date: '2015-02-09', value:'namew'},
{date: '1980-12-23', value:'name2'},
{date: '2015-02-12', value:'namen'},
{date: '2015-02-13', value:'named'}
];
var arrSeqErrors = [];
function funTestDates(){
var intLastValue = 0, intUnixDate =0;
for (x = 0; x <= arrData.length-1; x++){
intUnixDate = Date.parse(arrData[x].date)/1000;
var intResult = intUnixDate - intLastValue;
if (intResult < 0){
console.log("initeneration: " + x + " is out of sequence");
arrSeqErrors.push (arrData[x]);
}
intLastValue = intResult;
}
console.log("Items out of sequence are:");
console.log(arrSeqErrors);
}
funTestDates();
