Функция поиска в отсортированом масивве

[bas784]

Необходима функция поиска для массива Array
Есть ли она? И как её реализовать для 6-ого плеера?
То-еесть могу и сам написать но может у вас есть наработки какие-нибудь!!
Как говорится зачем изобретать велосипед?
Заранее спасибо за помощь!

[Hauts]

function searchInArray(arr, obj){
for(var i in arr){
if(arr[i] == obj){
return i
}
}
return -1
}


Типа такой? Для шестого плеера подойдет и так:

Array.prototype.search = function(obj) {
for (var i in this) {
if (this[i] == obj) {
return i;
}
}
return -1;
};
var a = ["a", "b", "c"];
trace(a.search("b"));

[bas784]

хм но здесь простой перебор! Мне нужно что нибудь пооптимальней
Функция очень критична для исполнения скрипта!
А комп слабый

[udaaff]

хм но здесь простой перебор! Мне нужно что нибудь пооптимальней
Функция очень критична для исполнения скрипта!
А комп слабый
Переходите на AS3.0 в таком случае.

[bas784]

С радостью но не могу привязан к 6-ому

[udaaff]

С радостью но не могу привязан к 6-ому
Ну тогда перебором :)

[bas784]

Мда чувствую нароботок не у кого нету придётся шерстить Кнута

[Hauts]

А какие еще могут быть наработки? Расскажите?

Зачем вам шестой плеер, когда уже есть десятый?

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

[bas784]

А)массив большой !
Б)Функция вызывается часто при перерасчёте!
В)Компьютер слабый
Г) Помимо плеера на нем лежат другие более важные задачи
Д) Заличензирован только 6-ой
И т д и т п
этот список можно продолжать .....

[Hauts]

Я вас понял. Можно попробовать присваивать ключ к объекту, и уже смотреть существование ключа в объекте, а не перебор массива. Например, так:

Array.prototype.addForSearch = function(obj, key) {
if (this.keysObject == undefined) {
this.keysObject = {};
}
//key = (!key) ? obj : key;
this.push(obj);
this.keysObject[key] = {id:this.length-1};
return this.length;
};
Array.prototype.searchByKey = function(key, returnObject) {
if (!this.keysObject) {
return -1;
}
if (this.keysObject[key] != undefined) {
if (this[this.keysObject[key].id] != undefined) {
if (returnObject) {
return this[this.keysObject[key].id];
}
return this.keysObject[key].id;
}
}
return -1;
};
var someArray = []
someArray.addForSearch({text:"One"}, 1)
someArray.addForSearch({text:"Two"}, 2)
someArray.addForSearch({text:"Three"}, 3)
someArray.addForSearch({text:"Four"}, 4)
someArray.addForSearch({text:"Five"}, 5)

trace(someArray.searchByKey(3)) // Второй номер в массиве, третий элемент
trace(someArray.searchByKey(3, true).text) // Вернет объект по ключу


В общем, исходя из конкретной задачи, можно придумать, как организовать поиск в массиве. Если известно, что в нем хранится (объекты, числа, строки?).

[alexcon314]

bas784, можно большой массив разбить на части по какому-то критерию и поиск вести только в части массива, можно подумать об индексации элементов массива, но это может усложнить процедуру добавления элементов в массив.
А от перебора (явного или неявного) вас здесь ничто не избавит.

[bas784]

Только зачем дополнительно использовать ключ? есть же индекс Array;
Вот по нему и ищем
var A=Array();
A[i]=Value;//i=KeyID

[Hauts]

Так вам поиск по ключу? Или по значению?

[bas784]

По значению опредилить индекс массива
Значения - числа

[Hauts]

Array.prototype.pushIndexed = function() {
if (this._indexes == undefined) {
this._indexes = [];
}
for (var i in arguments) {
this.push(arguments[i]);
this._indexes[arguments[i]] = i;
}
return this.length;
};
Array.prototype.searchIndexed = function(n:Number) {
return this._indexes[n];
};
var testArray = [];
testArray.pushIndexed(20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1);

trace(testArray.searchIndexed(15)); // 5
trace(testArray.searchIndexed(20)); // 0
trace(testArray.searchIndexed(1)); // 19
trace(testArray.searchIndexed(6)); // 14


При условии, что значения не повторяются.

[wvxvw]

Есть такая штука, как бинарное дерево, если для поиска элементов в упорядоченом массиве (ну, в данном случае, не массиве) - самый ИМО подходящий вариант.
Смысл реализации простой: в каждом элементе есть "переключатель" работающий по принципу "если условие выполнилось - перейти на индекс #, а если нет - перейти на индекс ##" - в таком случае витков цикла будет меньше (на сколько меньше - не скажу, но я думаю, хорошие люди уже это давно посчитали и описали в какой-нибудь википедии).

[bas784]

Интерестный подход с индексами в качестве значений. А можно ли перегрузить оператор = в Array ?

например


var a:Array;
//Чтобы например при выполнении
a[0]=23;
// Дополнительно записалось
a.Index[23]=0;

[Hauts]

var a = [];
a._indexes = [];

a[0] = 23;
a._indexes[23] = 0;


Ну вот как-то так. Надеюсь я вам помог.

[bas784]

К сожалению в моём случае в качестве значений в масиве выступают вещественные числа с разными знаками. Так что такая индексация не подходит.
Но в качестве будущей заметки на частный случай поиска уникальных чисел метод изложеный выше очень даже пригодиться. Так что конечно же спасибо за помощь.
А а мне чувствую придётся реализовать хотя бы тот же метод половивого деления.
Плохо что в библиотеках нет алгоритмов для поиска.

[Hauts]

var a = [];
a._indexes = {};
a[123] = -23.375;
a._indexes[-23.375] = 123;
trace(a._indexes[-23.375]); // 123


Не стоит отчаиваться. :)

[bas784]

Оказывается!
Если встретятся одинаковые значения оно всеравно опредилит одно из них
т.е. найдёт! Хм круто с.п.с.:)
Кстате какое максимальное значение индекса может быть в Array?

100 000 например?

[Hauts]

Сколько компьютер сможет, наверное :)

[wvxvw]

@Hauts:
Чесно говоря, я не знаю, как оно в AS1 / AS2, но в принципе поиск свойства через рефлекшн да еще и с подразумеваемой конвертацией числа в строку - ну как бы не не должно быстро бегать... хотя, кто его знает, как оно там сделано, может и остальные свойства объектов тоже через рефлекшн получаются.

Перегрузить оператор доступа к массиву можно... но, в плане скорости, лучше не будет, а, скорее всего ток хуже :) т.е. отнаследоваться от Array и определить классу __resolve() - но это чистой воды украшение, работать оно будет медленнее.

Из интересных деталей: HaXe может компилировать SWF v6, и в нем есть дополнительные реализации коллекций (например линейный список), который судя по тестам должен во преки теории бегать во флеше быстрее массива.

EDIT:
Максимальное значение, я так думаю, 0x7FFFFFFF, дальше скорее всего индексы будут записываться как строки, а не как числа. Вообще с массивом в AS не понятно, но больше максимума для 32-бит целого числа со знаком я бы не стал пробовать.

[bas784]

И вот ещё в чём програмируешь для адаптации с CS4 и где скачать? Может плаг какой есть для облегчения жизни програмиста
А то редактор CS4 до ума так и не довели да и отладка ещё со старых времён никакая.
Когда программа большая пусть даже и твоя начинаешь хвататься за голову!

[wvxvw]

http://www.flashdevelop.org/community/index.php (бесплатный)
http://sourceforge.net/projects/aseclipseplugin/ (бесплатный, но кажется, что поддержка / разработка закончилась довольно давно)
http://www.fdt.powerflasher.com/ (платный, но я понятия не имею как у них сейчас с поддержкой AS2...)

[bas784]

А что посоветуете для адаплации с CS4? для 6-ого
http://www.flashdevelop.org/community/index.php (бесплатный)

Добавлено через 3 минуты
Кстате какая версия а то последняя
http://www.flashdevelop.org/downloads/releases/FlashDevelop-3.0.6-RTM.exe
и что доолнительно нужно к ней?

[wvxvw]

3.0.6 RTM - это последняя, есть dev build, помоему, но разницы для вас не будет, изменения восновном касаются AS3 / HaXe.
Для AS2 вам ничего дополнительно не нужно, все вроде там уже и так должно быть.

[bas784]

Скачал вторую. И это редактор ? Мне бы что нибудь наподобе Visual.
Выпадающие списки и.т.д

[wvxvw]

Вторую что?
Visual - имеется в виду MS Visual Studio - ну так, конечно это не VS, но в чем-то даже похож немного, а в смысле автокомплита, так может даже и поудобнее будет...
Какие выпадающие списки? Флешевые компоненты чтоли? Если компоненты, то даже не знаю, есть адобовские, но они очень убогие... а других, так чтобы прямо набор - ну был порт SWing'a для AS2 - но это было много лет назад... может были какие-нибудь другие готовые решения, я уже просто не в курсе...

[bas784]

А почему у объекта типа Array в FlashDevelop нет конструктора
его нужно както подключить к проекту ???
a=Array(); // ошибка

По умолчанию
используется библиотека mtasc
Как её можно поменять на другую?

[udaaff]

var a:Array = new Array();
или
var a:Array = [];

[bas784]

первый вариант не работает почемуто

[udaaff]

Значит что-то не то делаете.

[wvxvw]

А почему у объекта типа Array в FlashDevelop нет конструктора
его нужно както подключить к проекту ???
a=Array(); // ошибка

По умолчанию
используется библиотека mtasc
Как её можно поменять на другую?

1. Потому что у Array нет конструктора.
2. FlashDevelop - это только редактор кода, AS2 написала компания Macromedia :)
В ФД есть интринсик классы нужные для автокомплита встроенных классов - покопайтесь в них, если вам так нравится использовать Array() - просто допишите его туда. (Только имейте в виду, что в вообще писать туда ничего не нужно обычно, и на то, как будер работать ваш код это никак не повлияет, т.е. если вы попробуете добавить произвольное свойство в интринсик класс, то у класса, который он заменяет это свойство не появится.

А другая - это FLASC чтоли? На что вы менять-то будете?
Если вы можете сами собрать ФД из сорцев, то можно перекомпилировать FDBuild модуль и в нем заменить пути к MTASC на что вам нужно. Если нет - отключите компиляцию вообще и в prebuild commands пропишите вызов вашего компилятора.

[bas784]

А какие возможности отладки в ФД? Кроме использования трасе конечно!

А то пытался объединить редактор с IDE Flash ничего не получилось!!

Кстате написал функцию поиска необходимую для моих целей!

//_root.ob=Array(10,30,50,60,70,80,100);
_root.ob=Array(100,80,70,60,50,30,10);

_root.NDir=-1;
Search=function(ob:Array,Value:Number):Number{
var p1:Number=0;
var p2:Number=ob.length-1;
var p1New:Number=p1;
var p2New:Number=p2;
if(ob[p2]*NDir<=Value*NDir) return p2;
if(ob[p1]*NDir>Value*NDir) return -1;
while(1){
if(ob[p1]==Value) return p1;
if(ob[p2]==Value) return p2;
if(p1==p2||p2==(p1+1))
return p1;
p2New=p2;
while(ob[p2New]*NDir>Value*NDir){
p2=p2New;
p2New=Math.floor(p1+(p2New-p1)/2);
trace("1: "+p2New+" "+ob[p2New]);
}
p1=p2New;// Новое начало
p1New=p1;
while(ob[p1New]*NDir<Value*NDir) {
p1=p1New;
p1New=p1New+Math.ceil((p2-p1New)/2);
trace("2: "+p1New+" "+ob[p1New]);
}
p2=p1New; //Новый конец

}
return -1;
}
trace(ob);
L=81;
F=Search(ob,L);

trace("Find("+L+") ob["+F+"]="+ob[F]);


Покрайней мере лучше чем простой перебор :)

[Hauts]

Попробуйте протестировать на скорость функции, которые в этой теме есть. Было бы интересно на результаты посмотреть.

Что-то я сомневаюсь, что два while внутри еще одного — это хорошее решение.

[udaaff]

Что-то я сомневаюсь, что два while внутри еще одного — это хорошее решение.
Особенно, с while(1) :)

[Hauts]

Ну... деликатность не помешает. :)

[bas784]

Главное что оно работать а два while внутри одного не такое уж плохое
решение. Меньше итераций.
По крайней мере с точки зрения языка Си :)

А на быстродействие смортря по каким критериям оценивать?
Мне например был нужен условный поиск на попадание числа в диапозон
значений.

[udaaff]

А на быстродействие смортря по каким критериям оценивать?
По времени естественно.

[bas784]

быстрее чем простой перебор для больших массивов!:)

Кстате вы можете проверить время работы и сами
пример рабочий.
P.S Чем лучше проц тем быстрее будет:).Поэтому нужен другой пример
выполняющий туже задачу условного поиска дикапозона. Только
я здесь таких не наблюдаю:quiet: