Форум Flasher.ru

Форум Flasher.ru (http://www.flasher.ru/forum/index.php)
-   ActionScript 3.0 (http://www.flasher.ru/forum/forumdisplay.php?f=83)
-   -   concat с удалением одинаковых элементов (http://www.flasher.ru/forum/showthread.php?t=152203)

Jewelz 13.03.2011 17:26

concat с удалением одинаковых элементов
 
есть 2 массива:
Код:

[
 Item1,
 Item2,
 Item3
]

Код:

[
 Item3,
 Item4,
 Item5
]

нужно объединить 2 массива и удалить оттуда одинаковые элементы, т.е. на выходе должно быть:
Код:

[
 Item1,
 Item2,
 Item3,
 Item4,
 Item5
]

как оптимальнее всего это сделать? сейчас сделано так: пробегаюсь по самому короткому из массивов, и ищу совпадение в другом массиве через indexOf, если нашли, то удаляем из первого, затем сцепляю оба, но думаю что можно оптимизировать

i.o. 13.03.2011 17:54

Сразу код:
Код AS3:

var arrA:Array = [ "Item1", "Item2", "Item3", "Item4" ];
var arrB:Array = [ "Item3", "Item3", "Item4", "Item5" ];
 
/*
// Вариант через создание нового массива
var arrRes:Array = arrA.concat( arrB );
var arrFinal:Array = [];
 
var s:String;
var i:int = -1;
var l:int = arrRes.length;
while( ++i < l )
{
        s = arrRes[i];
 
        if( arrFinal.indexOf( s ) < 0 )
                arrFinal.push( s );
}
 
trace( arrFinal ); // Item1,Item2,Item3,Item4,Item5
*/

 
// Вариант через модификацию существующего массива
var arrFinal:Array = arrA.concat( arrB );
var i:int = arrFinal.length;
while( i-- )
{
        if( arrFinal.indexOf( arrFinal[i] ) < i )
                arrFinal.splice( i, 1 );
}
 
trace( arrFinal ); // Item1,Item2,Item3,Item4,Item5


expl 13.03.2011 18:03

Цитата:

Код AS3:

arrFinal.indexOf( arrFinal[i] )


скорость работы indexOf зависит от количества элементов (проверял), если их больше 100 - лучше хеш (Dictionary) использовать.

Цитата:

// Вариант через создание нового массива
Ну дык через concat он тоже новый создается, может, вы конечно выиграете на нативном слиянии - но тут многое зависит от количества arrFinal.indexOf( arrFinal[i] ) и splice в первом и втором случае - короче пока не протестируешь производительность - не узнаешь

Jewelz 13.03.2011 18:11

я не написал, что в одном массиве не может быть одинаковых элементов, т.е. такой ситуации не будет:
Код AS3:

var arrB:Array = [ "Item3", "Item3", "Item4", "Item5" ];

поэтому сливать лучше в конце, видимо это самый оптимальный способ

i.o. 13.03.2011 18:13

Цитата:

Цитата:

// Вариант через создание нового массива
Ну дык через concat он тоже новый создается, может, вы конечно выиграете на нативном слиянии - но тут многое зависит от количества arrFinal.indexOf( arrFinal[i] ) и splice в первом и втором случае - короче пока не протестируешь производительность - не узнаешь
Специально два варианта предложил, чтобы не обвиняли в приверженности к одному из них. Так ведь и тут придрались... :)

GBee 13.03.2011 18:14

А массивы всегда отсортированы?

i.o. 13.03.2011 18:15

Цитата:

поэтому сливать лучше в конце, видимо это самый оптимальный способ
не понял, про что речь?

Jewelz 13.03.2011 18:18

Цитата:

Сообщение от GBee (Сообщение 980200)
А массивы всегда отсортированы?

нет, в разнобой
Цитата:

Сообщение от i.o. (Сообщение 980201)
не понял, про что речь?

речь о том, что можно проверить на вхождение только один из массивов, цикл получается меньше ~в 2 раза

i.o. 13.03.2011 18:22

тогда так:
Код AS3:

var arrA:Array = [ "Item1", "Item2", "Item3", "Item4" ];
var arrB:Array = [ "Item3", "Item4", "Item5" ];
 
var i:int = arrA.length;
while( i-- )
{
        if( arrB.indexOf( arrA[i] ) > -1 )
                arrA.splice( i, 1 );
}
 
var arrFinal:Array = arrA.concat( arrB );
trace( arrFinal ); // Item1,Item2,Item3,Item4,Item5


spooner 13.03.2011 18:32

Код AS3:

var i:int = arrA.length;
while( i-- ){}

Прикольная конструкция. Возьму на вооружение, спасибо.
ЗЫ: Извиняйте, что не в тему.

GBee 13.03.2011 19:22

Может попробовать бинарное дерево? Меньший налево, больший направо, равный игнорить. Оба массива в него, а потом обратно.


Часовой пояс GMT +4, время: 19:38.

Copyright © 1999-2008 Flasher.ru. All rights reserved.
Работает на vBulletin®. Copyright ©2000 - 2026, Jelsoft Enterprises Ltd. Перевод: zCarot
Администрация сайта не несёт ответственности за любую предоставленную посетителями информацию. Подробнее см. Правила.