Forum Webscript.Ru
Программирование => Perl => Тема начата: commander от 24 Марта 2005, 10:58:16
-
итак есть массив @arr_m - скольугодно большой...
нужно в массив @arr_n записать $n наибольших значений, при условии что $n <<(многоменьше) scalar(@arr_m)...
варианты?
-
#!/usr/bin/perl -w
my @arr_m=(1,11,22,3,4,5,6,7,8,99);
my $n=2;
my $i=$#arr_m;
my @arr_n=(sort {$a<=>$b} @arr_m)[($i-$n+1)..$i];
print (join("\\n",@arr_n));
-
Green Kakadu
я примерно тоже сначала написал... :)
а теперь пердтавь что у меня scalar(@arr_m) - девятизначное число... таким кодом ты повесишь любую тачку...
ещё варианты?
-
commander:
а теперь пердтавь что у меня scalar(@arr_m) - девятизначное число... таким кодом ты повесишь любую тачку...
ИМХО это самый оптимальный вариант, если ты собираешься оперировать с частями таких объемов данных, то тогда загоняй это в БД - пусть она мучается да и память не будешь этим монстром засорять. Сам по себе такой гигантский массив занимает весьма приличный размер памяти, без всяких операций.
-
Green Kakadu
это простая задачка... и вариант тут гипотетический... :)
ИМХО это самый оптимальный вариант
оптимальнее вариант покажу чуть попозже... :)
мне интересно варианты других... :)
-
Отсортируй на C каким-нибудь стандартным алгоритмом, запиши в файл, а потом считай n первых строк из отсортированного файла =)
-
2NetFly
интересное предложение ... но смысла особого не вижу... и что вы все так за сортировку зацепились? =)
-
commander:
оптимальнее вариант покажу чуть попозже...
интересно взглянуть..
-
Green Kakadu
терпение... :)
ну что больше предложений не последует?
Vlad, NeoNox ?
-
commander:
а теперь пердтавь что у меня scalar(@arr_m) - девятизначное число... таким кодом ты повесишь любую тачку.
Чувствую, что здесь не совсем верно задача поставлена.
Усли у тебя @arr_m девятизначное число не вешает тачку, то $n максимальных тоже не должны подвесить, если убирать их из исходного массива @arr_m то занятая память останется на том-же уровне.
-
NeoNox
Green Kakadu
2NetFly
вообще эта задача для С++ но по понятным причинам я её перевел для перла, конечно на перле такие вещи не делаються... :)
ИХМО правильный вариант на perl:
-----------------------------------------------------------------------------------------
#!/usr/bin/perl -w
use strict;
my @arr_m=(1,54,21,30,4,5,6,7,8,99);
my @arr_n;
my $n=2;
map {$arr_n[$_]=$arr_m[$_]} (0..$n);
for (my $i=$n; $i<=$#arr_m; $i++)
{
my $min_pos=0;
map {$min_pos=$_ if ($arr_n[$_]<$arr_n[$min_pos])} (0..$n);
$arr_n[$min_pos] = $arr_m[$i] if ($arr_n[$min_pos] < $arr_m[$i]);
}
------------------------------------------------------------------------
идея понятна?
а вот реализация этого на С++:
------------------------------------------------------------------------
#include
#define C_BIG_SIZE 15
#define C_SMALL_SIZE 5
int main(void)
{ // 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
int aSource[C_BIG_SIZE] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 64, 33, 45, 21 };
int aResult[5];
// Заполняем результат маленького массива первыми C_SMALL_SIZE значениями
for (int j = 0; j < C_SMALL_SIZE; j++) { aResult[j] = aSource[j]; }
// Проходим по всем элементам большого массива
for(int i = C_SMALL_SIZE; i < C_BIG_SIZE; i++)
{
// Ищем минимальный элемент в маленьком массиве
int iMinPos = 0;
for (int j = 0; j < C_SMALL_SIZE; j++)
{
if (aResult[j] < aResult[iMinPos]) { iMinPos = j; }
}
// Если найденны минимальный элемент меньше чем текущий элемент в большом массиве
// заменяем этот минимальный элемент на элемент из большого массива
if (aResult[iMinPos] < aSource) { aResult[iMinPos] = aSource; }
}
cout << "Result: ";
for (int j = 0; j < 5; j++) { cout << " " << aResult[j]; }
cout << endl;
}
--------------------------------------------------------------------------
P.S. задача мне очень понравилась...
кстати подобные задачи используються для тестирования программистов при приёме на работу в крупные компании... аля rambler... в частности задача была взята у них... :)
-
Мне кажется тут можно подумать о кольцевом буфере.
-
vladsu
а если по подробнее? :)
-
Сейчас позавтракаю и попробую изобразить.
-
гыы.... вообщем Влад, как всегда на высоте...
вот до чем кончилась дискуссия....
на этом коде я здался... :
-----------------------------------------------------------------------------------------------
#!/usr/bin/perl -w
use strict;
my @arr_m = map {rand $_} (0..1000000);
my @arr_n;
my $n = 5;
foreach ( @arr_m )
{
@arr_n = sort {$a <=> $b} @arr_n,$_ and next if ( @arr_n < $n );
next if $_ < $arr_n[0];
shift(@arr_n);
@arr_n = sort {$a <=> $b} @arr_n,$_;
}
print join "\\n", @arr_n;
-----------------------------------------------------------------------------------------------
:)