1

Topic: Sorting of an array according to other array

Greetings, are data array and there is a sorting array, for example:

const data = [
{id: 2, name: ' item 2 '},
{id: 1, name: ' item 1 '},
{id: 3, name: ' item 3 '}
];
const sortOrderById = [3, 2, 1];
const sortedData = sort (data, sortOrderById);
//sortedData = [
// {id: 3, name: ' item 3 '},
// {id: 2, name: ' item 2 '},
// {id: 1, name: ' item 1 '}
//];
function sort (data, sortOrderById) {
//???
}

the Simple decision to convert data in Map and transversing on sortOrderById to pull out values from this Map, approximately so:

function sort (data, sortOrderById) {
const itemsById = new Map (data.map (item => ([item.id, item])));
return sortOrderById.map (id => itemsById.get (id));
}

But here productivity is very important, data can contain ten thousand elements and the code runs on the server. If to me does not change storage, I where that for a long time for a long time, saw faster algorithm which allows to sort almost for one pass, I that confuse that, or such algorithm exists?

2

Re: Sorting of an array according to other array

3

Re: Sorting of an array according to other array

rew
To convert data in Map
It to you will cost N*log (N)
Transversing on sortOrderById to pull out values from this Map
Besides N*log (N)
That is the general complexity quits N*log (N). It is normal.
If to me does not change storage, I where that for a long time for a long time, saw faster algorithm which allows to sort almost for one pass, I that confuse that, or such algorithm exists?
Sorting with the linear complexity? No, it is any unscientific fantasy.
FUKS
And as "key" to palm off on it the same array sortOrderById "inside out": time in it are stored id, that is unique values, means it is possible to transform it to the associative array (for example keyOrder) in which original values will be indexes, and initial indexes - values.
So the same mirroring of that decision, which HARDWARE were offered itself:D by Him in  transforms data, and sorts out sortOrderById, and here on the contrary - sortOrderById in , and to sort out data. The same complexity.

4

Re: Sorting of an array according to other array

FUKS
It is what language?
javascript, but language is secondary, important algorithm.
Black Tiger
No, it is any unscientific fantasy.
Absolutely in any way?:shuffle:
On statements of the problem sortOrderById can contain, everything that helps sorting, data should not contain any data about the order and thus the data can periodically move in an array if is even more exact, after each change in object of the data, it is moved to the array end, but thus after sorting it should remain in the same place where the link to it is in an array sortOrderById if not clearly, a pseudocode piece:

const data = [
{id: 2, name: ' item 2 '};
{id: 1, name: ' item 1 '};
{id: 3, name: ' item 3 '}
];
function updateItem (id, name) {
const item = data.removeAndGetById (id);
item.name = name;
data.addLast (item);
}
updateItem (1, ' item 1 updated ')//{id: 1} it will be moved to the end data, but the order after sorting in sortedData remains the same

as sortOrderById it is updated only if the sorting order of objects exchanged that happens rarely, data can be updated very often and consequently to update sortOrderById after any change in data, not a variant.

5

Re: Sorting of an array according to other array

... We Tell so: at you the task not sortings, and indexings. That is on mind you sortOrderById is an index. If on the task to look so to obtain the sorted data for the linear time it is possible. But you what for imposed on the task some additional restrictions like that the data is stored in arrays, and the index cannot be updated at change of the data, and in such setting the task fine becomes complicated.

6

Re: Sorting of an array according to other array

Black Tiger
So the same mirroring of that decision, which HARDWARE itself offered
Yes, but the data each time different, their each time  it is necessary, and sorting order constant, const sortOrderById, once . Another matter what to get  from the associative array too time it is necessary, but here without variants.
And generally in what sense of sorting of the data? Them it is necessary in such sorted type all list [del] to announce [/del] somewhere to deduce or direct access to everyone  on an index is necessary? On sense a array data  to be associative, with keys in the necessary order:

 const data = {
2: {id: 2, name: ' item 2 '};
3: {id: 1, name: ' item 1 '};
1: {id: 3, name: ' item 3 '}
};

Then "sorting" will happen at the data sampling level, the built in means. Hardly here speech about  to system to which the fast simple array, instead of the slow associative is necessary. I guess that the array data simply is not subject to reconstruction, the decision is necessary within the limits of existing architecture.

7

Re: Sorting of an array according to other array

Black Tiger
But you what for imposed on the task some additional restrictions like that
It not I smile FUKS the decision is necessary within the limits of existing architecture. and to change architecture what to spare log (N), me hit and will be right smile
The index cannot be updated at change of the data it not it is impossible, but it too complicates
In what sense of sorting of the data? It is necessary to announce them in such sorted type all list somewhere to deduce
Abstractly, there is a task list which need to be fulfilled in the strict sequence, given each task can change and they immutable, therefore at changes of the data in tasks, the prior version is marked as remote, and in the end data the clone with changes is added, to interpose a clone not into the end it is impossible, is that api data stores (why so? Architecture such, record optimization). To add in task object a field order and to do sampling with sorting according to it regular request of storage, there would be an ideal variant, if not a necessity of possibility of cardinal change of sequence of tasks for one atomic operation. The storage does not support transaction, therefore even in a simple case if I need to move one task from the list end to the beginning, and the second task on the contrary, from the beginning in the end, there will be an interval of time, when execution order wrong and if it also . . Requirements to the order of tasks to guarantee the correct sequence always.
If there is what that ideas, will be glad smile

8

Re: Sorting of an array according to other array

How correspond maximum/minimum id and their amount in a sorting array?

9

Re: Sorting of an array according to other array

Warper
It uid, theoretically it grows at each new element, at an update existing it is copied. But if very much it is necessary, it is possible to add still a field, is conditional-any type.

10

Re: Sorting of an array according to other array

It is necessary to work the "intermediate" variant: notification message obtaining () from . If in the course of change it is possible to receive id tasks and its new index it can be registered in the correspondence table:

 CurrentId [taskId] =newIndex; 

And if id tasks a limited number it is possible even to make CurrentId not associative, but a normal array as offers Warper . But all the same the separate associative array for conversion id in an index (key) CurrentId is required.
And if to an indexable array it is possible to add a field here it can and be involved under "a reverse" index.

11

Re: Sorting of an array according to other array

If id go from 0 to N-1 (or from 1 to n) it is possible to make theoretically a reverse index on a normal array id-> position for a sorting array. After compilation of one such index it is possible to run a pack many sorted arrays, indexing on it. In case sorting array slightly more, it is possible to initialize  an array "temporary result", to put down elements present at a sorted array, and then to transit copying in final result only nonzero elements from an array "temporary result". Time of one pass on a sorted array will be O (N+M), where N - a number of elements of a sorted array, M - a number of elements of a sorting array.
Unfortunately, for javascript, yes with floating id, yes the associative arrays or  for an index id-> position, the reversal order id-> position in itself will be not less log (N). Compilation time  (successfully selected hashmap) can be O (N) at the best, so an initial variant not that it is bad - at a successful choice of structure ...

12

Re: Sorting of an array according to other array

I  speaking not  at what here sorting generally. In initial setting there is an array something there and an array already  with keys in the first array.
The task is only reduced to creation of an output array with elements  to keys in sortOrderById.
And this task trivial type b [i] = a [sortOrderById [i]],  sortOrderById serves as a reindexing array. In case of not monolithic id the task not strongly spoils since always it is possible to use implementation from so-called  arrays, or implementation with page .  O (N) and it it is very difficult to spoil here.

13

Re: Sorting of an array according to other array

vertur
Here there are additional conditions, after each change in any element in an array a, this element moves in the end of this array that demands to update as its index in sortOrderById and in view of that it is two operations and them it is impossible to make atomic or transactional, there will be time moment when the order of elements will be wrong (when the element was already moved to the array end a, and its index in sortOrderById contains still old value)

14

Re: Sorting of an array according to other array

rew
There will be time moment when the order of elements will be wrong (when the element was already moved to the array end a, and its index in sortOrderById contains still old value)
Do so:
1) in the array end write down the modified copy of N th element. It while will be not accessible through SortOrderById.
2) in SortOrderById switch a position of the changed element from an old place on last in an array. Everything, the old element ceased to be addressed through SortOrderById and the modified copy, on the contrary, became. Elementary quality.
3) now the old element can be deleted from an array.

15

Re: Sorting of an array according to other array

KPAH
Thanks, good variant, it is necessary to try to make POC.

16

Re: Sorting of an array according to other array

rew
After each change in any element in an array a, this element moves in the end of this array that demands to update as its index in sortOrderById,
I can that , but the intermediate sorted array of indexes just and is necessary not to move array cells of the data (that presumably is  operation).

17

Re: Sorting of an array according to other array

Konstantin Mironovich
That presumably is  operation
[off] cheap [/off]