Перасоўванне сегмента масіва ў межах масіва

Калі ў мяне ёсць масіў элементаў:

1, 2, 3, 4, 5, 6, 7, 8

Я хачу, каб выбраць дыяпазон элементаў і перамясціць іх у іншае месца ў масіве. Напрыклад:

1, 2, 5, 6, 7, 3, 4, 8

Тут 5, 6, 7 сегмент быў перамешчаны ў індэкс 2.

Які самы эфектыўны спосаб зрабіць гэта, у прыватнасці, каб абмежаваць колькасць дадатковых асобнікаў масіва. У мяне ёсць версія працуе, але гэта неэфектыўна і ўтварае цэнтральную ролю ў маім алгарытме, які я спрабую аптымізаваць.

Дзякуючы.

2
@Scott - True. Я праверыў гэта ў аналізе прадукцыйнасці на VS2012 і пацвердзіў, што ён марнуе вялікую частку свайго часу ў гэтым метадзе масіва ператасоўкі. Проста працаваць свой шлях праз некалькі прапаноў, каб убачыць, калі гэта робіць істотную розніцу.
дададзена аўтар Barguast, крыніца
@Scott - True. Я праверыў гэта ў аналізе прадукцыйнасці на VS2012 і пацвердзіў, што ён марнуе вялікую частку свайго часу ў гэтым метадзе масіва ператасоўкі. Проста працаваць свой шлях праз некалькі прапаноў, каб убачыць, калі гэта робіць істотную розніцу.
дададзена аўтар Barguast, крыніца
@Scott. Гэтая частка паўтараецца больш 1000000 раз у перспектыве, таму я хачу, каб аптымізаваць яго як мага больш. Гэта, вядома, самая павольная частка агульнай працы на сённяшні дзень.
дададзена аўтар Barguast, крыніца
@Scott. Гэтая частка паўтараецца больш 1000000 раз у перспектыве, таму я хачу, каб аптымізаваць яго як мага больш. Гэта, вядома, самая павольная частка агульнай працы на сённяшні дзень.
дададзена аўтар Barguast, крыніца
Магчыма, гэта больш складаная аперацыя, чым гэта можа здацца на першы погляд. Я спрабаваў абгарнуць маю галаву вакол яго на працягу некалькіх гадзін. У мяне ёсць версія гэтага, што працуе, але яна ўключае ў сябе выманне сегмента для перамяшчэння, ствараючы масіў астатку, і рекомбинировать іх пасля атрымання пазіцыі зноў ўставіць. Там павінна быць лепш. Дзякуй за вашыя каментары.
дададзена аўтар Barguast, крыніца
Магчыма, гэта больш складаная аперацыя, чым гэта можа здацца на першы погляд. Я спрабаваў абгарнуць маю галаву вакол яго на працягу некалькіх гадзін. У мяне ёсць версія гэтага, што працуе, але яна ўключае ў сябе выманне сегмента для перамяшчэння, ствараючы масіў астатку, і рекомбинировать іх пасля атрымання пазіцыі зноў ўставіць. Там павінна быць лепш. Дзякуй за вашыя каментары.
дададзена аўтар Barguast, крыніца
Колькасць раз, гэта называецца не мае значэння, просты прыклад Int J = 0; для (INT I = 0; я <1000000; я ++) {J = я;} Thread.Sleep (100000); , які заняў больш часу, пятлю або сон? Паглядзіце на тое, што зрабіў% профайлер кажа вам, што марнаваў у гэтым раздзеле, вы можаце быць няправільна пра час, праведзеным. Паглядзіце на гэтага MSDN Magazine артыкула і запусціць хуткі тэст. Калі я не мае рацыю, і ты мае рацыю, то вашы інстынкты, дзе добра. Па меншай меры, вы будзеце ведаць, замест таго, каб гадаць.
дададзена аўтар Scott Chamberlain, крыніца
Колькасць раз, гэта называецца не мае значэння, просты прыклад Int J = 0; для (INT I = 0; я <1000000; я ++) {J = я;} Thread.Sleep (100000); , які заняў больш часу, пятлю або сон? Паглядзіце на тое, што зрабіў% профайлер кажа вам, што марнаваў у гэтым раздзеле, вы можаце быць няправільна пра час, праведзеным. Паглядзіце на гэтага MSDN Magazine артыкула і запусціць хуткі тэст. Калі я не мае рацыю, і ты мае рацыю, то вашы інстынкты, дзе добра. Па меншай меры, вы будзеце ведаць, замест таго, каб гадаць.
дададзена аўтар Scott Chamberlain, крыніца
Вы ўпэўненыя, што вам трэба аптымізаваць дзеючы запыт? Гэта непрымальна павольна прама зараз, і нават тэсты прадукцыйнасці паказваюць, вы гэта дзе спад быў? Час, якое вы прымаеце, спрабуючы высветліць, як аптымізаваць гэты раздзел коды можа заняць больш часу, чым увесь час вы будзеце эканоміць на працягу ўсяго тэрміну службы праграмнага забеспячэння.
дададзена аўтар Scott Chamberlain, крыніца
Вы ўпэўненыя, што вам трэба аптымізаваць дзеючы запыт? Гэта непрымальна павольна прама зараз, і нават тэсты прадукцыйнасці паказваюць, вы гэта дзе спад быў? Час, якое вы прымаеце, спрабуючы высветліць, як аптымізаваць гэты раздзел коды можа заняць больш часу, чым увесь час вы будзеце эканоміць на працягу ўсяго тэрміну службы праграмнага забеспячэння.
дададзена аўтар Scott Chamberlain, крыніца
Любы алгарытм капіявання будзе O (п) - кожны элемент ўнутры рэгіёну, які ўплывае неабходнасць быць скапіяваная адзін раз ... Калі вы не можаце пазбегнуць капіявання наогул там не так шмат аптымізацый вы можаце зрабіць.
дададзена аўтар Alexei Levenkov, крыніца
Любы алгарытм капіявання будзе O (п) - кожны элемент ўнутры рэгіёну, які ўплывае неабходнасць быць скапіяваная адзін раз ... Калі вы не можаце пазбегнуць капіявання наогул там не так шмат аптымізацый вы можаце зрабіць.
дададзена аўтар Alexei Levenkov, крыніца
@KenoguLabz: у гэтым выпадку вы хочаце skiplist.
дададзена аўтар user7116, крыніца
Ці заўсёды вы рухацца ў зваротным кірунку, як гэта? Ці вы часам рухацца наперад? Нападаючыя моцна адрозніваецца (вашыя паказчыкі на самай справе не існуе, паколькі яны былі)
дададзена аўтар user7116, крыніца
@KenoguLabz: у гэтым выпадку вы хочаце skiplist.
дададзена аўтар user7116, крыніца
Наколькі вялікі ваш масіў? Вам таксама трэба аптымізаваць прастору?
дададзена аўтар Max, крыніца
Наколькі вялікі ваш масіў? Вам таксама трэба аптымізаваць прастору?
дададзена аўтар Max, крыніца
Я проста зразумеў, што звязаны спіс <�я> робіць </я> мае адно істотнае перавага ў параўнанні з масівам: не капіявання масіва, які з'яўляецца адным з асноўных мэт дадзенага пытання. Звязанае рашэнне спісу будзе значна больш <�я> памяць эфектыўнага , які можа ліквідаваць вузкае месца Barguast ст.
дададзена аўтар Kenogu Labz, крыніца
Абыходзе звязаны спіс будзе O (п), таксама, так што ідэя не атрымоўваецца даволі хутка, як добра.
дададзена аўтар Kenogu Labz, крыніца
Абыходзе звязаны спіс будзе O (п), таксама, так што ідэя не атрымоўваецца даволі хутка, як добра.
дададзена аўтар Kenogu Labz, крыніца
Што рабіць, калі вы выкарыстоўвалі дрэва ці іншую звязаную структуру? Проста папярэдняя думка, але вы можаце быць у стане рухацца рэчы вакол па больш нізкай кошту, у залежнасці ад таго, вы прымаеце элементы па індэксе або па значэнні. Зноў жа, маючы на ​​rejuggle элементы дрэва на кожны ход, верагодна, будзе не вельмі эфектыўны па часе, альбо ...
дададзена аўтар Kenogu Labz, крыніца
Што рабіць, калі вы выкарыстоўвалі дрэва ці іншую звязаную структуру? Проста папярэдняя думка, але вы можаце быць у стане рухацца рэчы вакол па больш нізкай кошту, у залежнасці ад таго, вы прымаеце элементы па індэксе або па значэнні. Зноў жа, маючы на ​​rejuggle элементы дрэва на кожны ход, верагодна, будзе не вельмі эфектыўны па часе, альбо ...
дададзена аўтар Kenogu Labz, крыніца
Але вам прыйдзецца паўторна Джиггер skiplist кожны раз, таксама, так што не атрымоўваецца, а таксама. Любы дапаможны сачыльны індэкс павінен быць переиндексирован кожны раз, калі Подсписок перамяшчаецца.
дададзена аўтар Kenogu Labz, крыніца
Але вам прыйдзецца паўторна Джиггер skiplist кожны раз, таксама, так што не атрымоўваецца, а таксама. Любы дапаможны сачыльны індэкс павінен быць переиндексирован кожны раз, калі Подсписок перамяшчаецца.
дададзена аўтар Kenogu Labz, крыніца

7 адказы

Паспрабуйце выкарыстоўваць звязаны спіс. Паколькі вы рухаецеся падраздзелы спісу, гэта будзе нашмат менш памяці, каб перамясціць спасылкі на абодвух канцах подсписка чым скапіяваць кожны асобны элемент у тым жа подсписке. Агульны час, складанасць аднолькавая (Θ (п) для абыходу звязанага спісу, Q (п) для капіявання масіва сегментаў), але вы будзеце мець больш памяці-складанасці (пастаянная п, у адрозненне ад Q (п)) і менш праблем з пастаяннай памяці выдзялення/адмацаванне.

3
дададзена

Адзін з падыходаў будуць нарэжце з пунктаў, якія павінны рухацца, а затым перанесці існуючыя элементы:

// T[] source
// int dest
// int start, end
T[] slice = new T[end - start];
Array.Copy(source, start, slice, 0, slice.Length);

if (dest < start)
{
   //push towards end
    Array.Copy(source, dest, source, dest + slice.Length, start - dest);
}
else
{
   //push towards start
   //who moves where? Assumes dest..dest+count goes left
    Array.Copy(source, end, source, dest, dest - start);
}

Array.Copy(slice, 0, source, dest, slice.Length);
2
дададзена
Пасля таго, як сесці з кавалкам паперы і чарчэння ўсё гэта, я ў канчатковым выніку ў канчатковым выніку з кодам, які ў значнай ступені адпавядае гэтаму. Я думаю, што гэта, верагодна, самае лепшае рашэнне. дзякуй.
дададзена аўтар Barguast, крыніца
Гэта ~ 350% хутчэй пры нагрузачнага тэставання :)
дададзена аўтар Barguast, крыніца
Я не ведаю, калі гэта змяніла б што-небудзь, але калі вы выкарыстоўваеце ALUE тыпаў вы можаце паглядзець Buffer.BlockCopy замест Array.Copy .
дададзена аўтар user7116, крыніца
Калі вы сапраўды хочаце, каб паскорыць працэс, Barguast, ён глядзіць на мяне, як вы можаце патроіць прадукцыйнасць яшчэ раз па гэтай схеме Array.Copy. Вам проста трэба будзе напісаць логіку, каб зрабіць пераход самастойна, захоўваючы ссунутыя элементы ў часовым зменных (толькі адзін ці два будзе рабіць) і вырашыць, ці вы хочаце перанесці рэчы наперад або назад, як вы хочаце апрацоўваць модульнымі/абгортку -around сітуацыі, і г.д. метады зруху будзе рабіць добрыя метады пашырэння для масіваў.
дададзена аўтар Iucounu, крыніца
Падобна на тое, што прадукцыйнасць з дапамогай прамога доступу да масіву будзе прыкладна ў 2-3 разы лепш, чым выклік Array.Copy() тры разы ў прыведзеным вышэй прыкладзе, у залежнасці ад канкрэтнай рэалізацыі.
дададзена аўтар Iucounu, крыніца

Адзін з падыходаў будуць нарэжце з пунктаў, якія павінны рухацца, а затым перанесці існуючыя элементы:

// T[] source
// int dest
// int start, end
T[] slice = new T[end - start];
Array.Copy(source, start, slice, 0, slice.Length);

if (dest < start)
{
   //push towards end
    Array.Copy(source, dest, source, dest + slice.Length, start - dest);
}
else
{
   //push towards start
   //who moves where? Assumes dest..dest+count goes left
    Array.Copy(source, end, source, dest, dest - start);
}

Array.Copy(slice, 0, source, dest, slice.Length);
2
дададзена
Пасля таго, як сесці з кавалкам паперы і чарчэння ўсё гэта, я ў канчатковым выніку ў канчатковым выніку з кодам, які ў значнай ступені адпавядае гэтаму. Я думаю, што гэта, верагодна, самае лепшае рашэнне. дзякуй.
дададзена аўтар Barguast, крыніца
Гэта ~ 350% хутчэй пры нагрузачнага тэставання :)
дададзена аўтар Barguast, крыніца
Я не ведаю, калі гэта змяніла б што-небудзь, але калі вы выкарыстоўваеце ALUE тыпаў вы можаце паглядзець Buffer.BlockCopy замест Array.Copy .
дададзена аўтар user7116, крыніца
Калі вы сапраўды хочаце, каб паскорыць працэс, Barguast, ён глядзіць на мяне, як вы можаце патроіць прадукцыйнасць яшчэ раз па гэтай схеме Array.Copy. Вам проста трэба будзе напісаць логіку, каб зрабіць пераход самастойна, захоўваючы ссунутыя элементы ў часовым зменных (толькі адзін ці два будзе рабіць) і вырашыць, ці вы хочаце перанесці рэчы наперад або назад, як вы хочаце апрацоўваць модульнымі/абгортку -around сітуацыі, і г.д. метады зруху будзе рабіць добрыя метады пашырэння для масіваў.
дададзена аўтар Iucounu, крыніца
Падобна на тое, што прадукцыйнасць з дапамогай прамога доступу да масіву будзе прыкладна ў 2-3 разы лепш, чым выклік Array.Copy() тры разы ў прыведзеным вышэй прыкладзе, у залежнасці ад канкрэтнай рэалізацыі.
дададзена аўтар Iucounu, крыніца

Я ведаю, што вы выбралі адказ; але гэтае пытанне сапраўды патрапіў пад маю скуру; каб убачыць, калі гэта магчыма, каб напісаць гэта па-іншаму.

Так што я прыдумаў гэты код:

static int[] MoveSlice(int[] arr, int startIndex, int length, int newIndex)
{
    var delta = (int)Math.Abs(newIndex - startIndex);

    if (delta >= length)
    {
        for (var i = 0; i < length; i++)
        {
            var swap = arr[startIndex + i];
            arr[startIndex + i] = arr[newIndex + i];
            arr[newIndex + i] = swap;
        }
    }
    else
    {
        var newStart = newIndex + length;

        for (var i = 0; i < delta; i++)
        {
            var swap = arr[newStart + i];
            arr[newStart + i] = arr[newIndex + i];
            arr[newIndex + i] = swap;
        }

        var l = (int)Math.Abs(length - delta);
        arr = MoveSlice(arr, newIndex + delta, l, newIndex);
    }

    return arr;
}

Я не тэставаў прадукцыйнасць яшчэ. Але я атрымліваў асалоду ад яе рашэння!

Магчыма, вам трэба выкарыстоўваць больш коды для праверкі магчымых памылак на межах і таму падобныя.

1
дададзена
Гэта некалькі падобна на маю першую спробу, перш чым я адказваў на гэтае пытанне. Гэта зманліва складана праблема! Дзякуючы.
дададзена аўтар Barguast, крыніца
Я толькі заўважыў, што праграма правёў больш часу ў метадзе, чым мне спадабалася, і задавалася пытаннем, што «лепшы» спосаб зрабіць гэта было. Я ў асноўным хацеў, каб захаваць копіі і свопы да мінімуму. Я не зрабіў поўнае параўнання паміж маім арыгінальным метадам, і маім бягучых (гл адказу sixlettervariables '), але код імчыць прыкметна хутчэй.
дададзена аўтар Barguast, крыніца
Калі вы выкарысталі гэта; быў карысны? Як наконт прадукцыйнасці?
дададзена аўтар Kaveh Shahbazian, крыніца
Я чакаў, што гэта будзе хутчэй, бо няма ніводнай копіі масіва. Але я думаю - наколькі мой розум можа пайсці - свопы ў тут знаходзяцца на мінімальным узроўні.
дададзена аўтар Kaveh Shahbazian, крыніца
І памятайце, што (ІМХО) пры тэставанні прадукцыйнасці метады: 1 - выключыць першы выклік (з-за рэчы, JIT рабіць па першым клічы) 2 - паўтарыць яго ў вялікай колькасці (скажам, 100000) і падзяліць усе затрачаны час да 100000.
дададзена аўтар Kaveh Shahbazian, крыніца

Я ведаю, што вы выбралі адказ; але гэтае пытанне сапраўды патрапіў пад маю скуру; каб убачыць, калі гэта магчыма, каб напісаць гэта па-іншаму.

Так што я прыдумаў гэты код:

static int[] MoveSlice(int[] arr, int startIndex, int length, int newIndex)
{
    var delta = (int)Math.Abs(newIndex - startIndex);

    if (delta >= length)
    {
        for (var i = 0; i < length; i++)
        {
            var swap = arr[startIndex + i];
            arr[startIndex + i] = arr[newIndex + i];
            arr[newIndex + i] = swap;
        }
    }
    else
    {
        var newStart = newIndex + length;

        for (var i = 0; i < delta; i++)
        {
            var swap = arr[newStart + i];
            arr[newStart + i] = arr[newIndex + i];
            arr[newIndex + i] = swap;
        }

        var l = (int)Math.Abs(length - delta);
        arr = MoveSlice(arr, newIndex + delta, l, newIndex);
    }

    return arr;
}

Я не тэставаў прадукцыйнасць яшчэ. Але я атрымліваў асалоду ад яе рашэння!

Магчыма, вам трэба выкарыстоўваць больш коды для праверкі магчымых памылак на межах і таму падобныя.

1
дададзена
Я толькі заўважыў, што праграма правёў больш часу ў метадзе, чым мне спадабалася, і задавалася пытаннем, што «лепшы» спосаб зрабіць гэта было. Я ў асноўным хацеў, каб захаваць копіі і свопы да мінімуму. Я не зрабіў поўнае параўнання паміж маім арыгінальным метадам, і маім бягучых (гл адказу sixlettervariables '), але код імчыць прыкметна хутчэй.
дададзена аўтар Barguast, крыніца
Гэта некалькі падобна на маю першую спробу, перш чым я адказваў на гэтае пытанне. Гэта зманліва складана праблема! Дзякуючы.
дададзена аўтар Barguast, крыніца
Калі вы выкарысталі гэта; быў карысны? Як наконт прадукцыйнасці?
дададзена аўтар Kaveh Shahbazian, крыніца
І памятайце, што (ІМХО) пры тэставанні прадукцыйнасці метады: 1 - выключыць першы выклік (з-за рэчы, JIT рабіць па першым клічы) 2 - паўтарыць яго ў вялікай колькасці (скажам, 100000) і падзяліць усе затрачаны час да 100000.
дададзена аўтар Kaveh Shahbazian, крыніца
Я чакаў, што гэта будзе хутчэй, бо няма ніводнай копіі масіва. Але я думаю - наколькі мой розум можа пайсці - свопы ў тут знаходзяцца на мінімальным узроўні.
дададзена аўтар Kaveh Shahbazian, крыніца

Калі вы хочаце, каб пазбегнуць стварэння копій масіваў дзеля эфектыўнасці, вы можаце пазбегнуць іх наогул. Вы можаце выкарыстоўваць як мінімум зменных для асобных значэнняў для перамяшчэння элементаў у іх новых напрамкі. Такі алгарытм вельмі эфектыўны ў памяці, і можа быць эфектыўным і ў цэлым, хоць гэта, відавочна, не можа скарыстацца родным, эфектыўным капіяваннем масіва.

0
дададзена

Калі вы хочаце, каб пазбегнуць стварэння копій масіваў дзеля эфектыўнасці, вы можаце пазбегнуць іх наогул. Вы можаце выкарыстоўваць як мінімум зменных для асобных значэнняў для перамяшчэння элементаў у іх новых напрамкі. Такі алгарытм вельмі эфектыўны ў памяці, і можа быць эфектыўным і ў цэлым, хоць гэта, відавочна, не можа скарыстацца родным, эфектыўным капіяваннем масіва.

0
дададзена