LINQ-dagi Recursive uslublar guruhini aylantirish Yupiter usulini tanlang

Menda shunday bir sinf bor:

public class SourceObject
{
    public string Id { get; set; }
    public List Children { get; set; }

    public SourceObject()
    {
        Children = new List();
    }
}

Ko'rib turganingizdek, u xuddi shu sinfning boshqa misollarini o'z ichiga olgan xususiyatlarga ega. Men bu sinfga tegishli ma'lumotlar menda ishlaydigan vaqtgacha bolalar soni noma'lum, natijada ob'ektning grafigi umumiy "chuqurlik" ham noma'lum.

SourceObject ob'ektlar grafiğinden xuddi shunday shakllangan grafigacha DestinationObject (AutoMapper bir ob'ektdan ikkinchisiga qanday o'xshash bo'lishi mumkinligiga o'xshash) uchun "xaritalash" .

Manba grafigimdan maqsad grafigiga joylashtiradigan usul bor, ammo bu usulda recursion ishlatiladi:

// Recursive way of mapping each Source object to Destination
public static DestinationObject MapSourceToDestination(SourceObject source)
{
    var result = new DestinationObject();
    result.Id = source.Id;
    result.Children = source.Children.Select(MapSourceToDestination).ToList();
    return result;
}

Biroq, manba obyekti grafigi kattaligi juda katta yoki chuqur bo'lmasa, bu juda yaxshi ishlaydi, ammo manba obyekti grafigi juda katta bo'lsa, bu uslub StackOverflow istisnolarini tashlaydi.

Ushbu funktsiyani muqobil nusxasini yaratishga muvaffaq bo'ldim va u o'z navbatini "Queue/Stack" bilan o'zgartiradi va " ushbu sahifada tasvirlanganga o'xshash texnikani qo'llaydi. javob berish ), shunga qaramasdan, Queue/Stack-ning ham juda katta bo'lishi mumkinligini tushunib etdim va mening bajarishim eng samarali ekanligiga ishonchim komil emas.

Yineleyicik funksiyani yineleyani manba obyekti grafigiga (ya'ni, takrorlashni olib tashlash va ideal tarzda, navbat/birikma) ishlatish uchun aylantirish mumkinmi?

3
qo'shib qo'ydi muallif Ivan Stoev, manba
@xanatos Shubhasiz, bilasiz :) Siz nima uchun siz N-suyak echimini talab qilayotganingizni tushunolmaysiz. Yoki siz IEnumerator qismini etishmayotgansiz yoki bilmayman. Haqiqatan ham, N - eng yomon holatdir (butun to'siq bitta bolaga ega bo'lgan yagona boladan iborat bo'lgan), ammo daraxtning o'rtacha maksimal chuqurlikda (yoki balandligida) Muhokama uchun rahmat, taqdir.
qo'shib qo'ydi muallif Ivan Stoev, manba
@xanatos Shubhasiz, bilasiz :) Siz nima uchun siz N-suyak echimini talab qilayotganingizni tushunolmaysiz. Yoki siz IEnumerator qismini etishmayotgansiz yoki bilmayman. Haqiqatan ham, N - eng yomon holatdir (butun to'siq bitta bolaga ega bo'lgan yagona boladan iborat bo'lgan), ammo daraxtning o'rtacha maksimal chuqurlikda (yoki balandligida) Muhokama uchun rahmat, taqdir.
qo'shib qo'ydi muallif Ivan Stoev, manba
@xanatos Birinchidan, siz ko'rmaydigan barcha ota-onalar va bolalar, shu jumladan, butun majmua (jb jadvali kabi) uchun kirishingiz mumkin deb taxmin qilyapsiz. Ikkinchidan, agar sizda kirishingiz bo'lsa ham, siz to'ldirish va xotira muammosini hal qilasiz, lekin vaqt masalasida ishlaydi. Va nihoyat, taklif qiladigan yechim Stack > dan foydalanadi va eng yomon holatda 2 * chuqurlik elementi bo'ladi - chuqurligi b> N dan foydalaning.
qo'shib qo'ydi muallif Ivan Stoev, manba
@xanatos Birinchidan, siz ko'rmaydigan barcha ota-onalar va bolalar, shu jumladan, butun majmua (jb jadvali kabi) uchun kirishingiz mumkin deb taxmin qilyapsiz. Ikkinchidan, agar sizda kirishingiz bo'lsa ham, siz to'ldirish va xotira muammosini hal qilasiz, lekin vaqt masalasida ishlaydi. Va nihoyat, taklif qiladigan yechim Stack > dan foydalanadi va eng yomon holatda 2 * chuqurlik elementi bo'ladi - chuqurligi b> N dan foydalaning.
qo'shib qo'ydi muallif Ivan Stoev, manba
@Evk bilaman (garchi u ). Ammo bu echim Erikning bajarilishidan farq qiladi va stok kattaligi daraxtning chuqurligi va IMO eng maqbuldir. OBga omad tilaymiz :)
qo'shib qo'ydi muallif Ivan Stoev, manba
@Evk bilaman (garchi u ). Ammo bu echim Erikning bajarilishidan farq qiladi va stok kattaligi daraxtning chuqurligi va IMO eng maqbuldir. OBga omad tilaymiz :)
qo'shib qo'ydi muallif Ivan Stoev, manba
qo'shib qo'ydi muallif Ivan Stoev, manba
@ IvanStoev OP suyaksiz echim so'raydi.
qo'shib qo'ydi muallif Evk, manba
@ IvanStoev OP suyaksiz echim so'raydi.
qo'shib qo'ydi muallif Evk, manba
@IvanStoev Multi-iterativ yechim mumkin ... Men yozganimdek ... Siz butun yechimni bir necha marotaba qayta ko'rib chiqdingiz ...
qo'shib qo'ydi muallif xanatos, manba
@IvanStoev Multi-iterativ yechim mumkin ... Men yozganimdek ... Siz butun yechimni bir necha marotaba qayta ko'rib chiqdingiz ...
qo'shib qo'ydi muallif xanatos, manba
@bud (eng katta holatda Stack <> ) Count = n - 1 qiymatiga ega bo'lgan (bir sidenote sifatida) qo'shilaman, bu erda n - elementlar soni ... Shunday qilib, xotirada (masalan, Ro'yxat <> ), siz juda ko'p xotirani (ortiqcha Ro'yxat <> ). 1,000,000 ta katta stack 8mb xotira (64 bitda) bo'lishi kerak ... bu raqamni berish uchun (texnik jihatdan u 16 mb xotira bo'lishi mumkin, chunki Stack <> ehtimol ikki baravar ko'payadi, shuning uchun 200000 ta element mavjud)
qo'shib qo'ydi muallif xanatos, manba
@bud (eng katta holatda Stack <> ) Count = n - 1 qiymatiga ega bo'lgan (bir sidenote sifatida) qo'shilaman, bu erda n - elementlar soni ... Shunday qilib, xotirada (masalan, Ro'yxat <> ), siz juda ko'p xotirani (ortiqcha Ro'yxat <> ). 1,000,000 ta katta stack 8mb xotira (64 bitda) bo'lishi kerak ... bu raqamni berish uchun (texnik jihatdan u 16 mb xotira bo'lishi mumkin, chunki Stack <> ehtimol ikki baravar ko'payadi, shuning uchun 200000 ta element mavjud)
qo'shib qo'ydi muallif xanatos, manba
@IvanStoev Stack <> dan foydalanadigan, shuning uchun ideal tarzda, navbat/Stack
qo'shib qo'ydi muallif xanatos, manba
@IvanStoev Stack <> dan foydalanadigan, shuning uchun ideal tarzda, navbat/Stack
qo'shib qo'ydi muallif xanatos, manba
@IvanStoev Men kosmosda O (N) ni (eng yomon ishni) almashtirayotganimni bilaman (siz taklif qilgan Stack, ya'ni Stack bilan O (N ^ 2) (Ro'yxatning bir necha marta qayta ko'rib chiqiladi). Esda tutingki, har ikkala echim amalga oshirilgan/qoldirilgan (yoki hech bo'lmaganda "bajarilgan" bayroq uchun) O (N)
qo'shib qo'ydi muallif xanatos, manba
@IvanStoev Men kosmosda O (N) ni (eng yomon ishni) almashtirayotganimni bilaman (siz taklif qilgan Stack, ya'ni Stack bilan O (N ^ 2) (Ro'yxatning bir necha marta qayta ko'rib chiqiladi). Esda tutingki, har ikkala echim amalga oshirilgan/qoldirilgan (yoki hech bo'lmaganda "bajarilgan" bayroq uchun) O (N)
qo'shib qo'ydi muallif xanatos, manba
Ha, mumkin, ammo hamma narsani bir necha marotaba qayta ko'rib chiqish kerak ... Masalan, sizda 1, 2, 3 va 1 raqamlaringiz 3 ga bog'liq bo'lgan bo'lsa, unda siz shunday qila olasiz: 1 (hal qilinmagan bog'liqliklar bor, (endi hal qilinmagan qaramlik mavjud), 2 (hal qilish), 1 ga qaytish (hal qilish), 1 (hal qilish)
qo'shib qo'ydi muallif xanatos, manba

8 javoblar

Men hali ham katta hajmdagi suyakka daraxtning maksimal chuqurligi maqbul umumiy echim ekaniga ishonaman.

Qizig'i shundaki, ma'lumotlar strukturasi va konkret jarayoni faqat Children.Count ga asoslangan holda aylantirilishini aniqlashtirish uchun barcha zarur ma'lumotlarni o'z ichiga oladi. Nima kerakligini ko'rib chiqaylik:

(1) Are there more source children to process: source.Children.Count != target.Children.Count)

(2) Which is the next source child to process: source.Children[target.Children.Count]

(3) What is the current processing child index: target.Children.Count - 1

Yuqoridagi qoidalar qayta ishlash vaqtida har qanday darajaga nisbatan qo'llanishi mumkin.

Mana, amalga oshirish:

public static DestinationObject MapSourceToDestination(SourceObject source)
{
   //Map everything except childen
    Func primaryMap = s => new DestinationObject
    {
        Id = s.Id,
       //...
        Children = new List(s.Children.Count)//Empty list with specified capacity
    };

    var target = primaryMap(source);

    var currentSource = source;
    var currentTarget = target;
    int depth = 0;
    while (true)
    {
        if (currentTarget.Children.Count != currentSource.Children.Count)
        {
           //Process next child
            var sourceChild = currentSource.Children[currentTarget.Children.Count];
            var targetChild = primaryMap(sourceChild);
            currentTarget.Children.Add(targetChild);
            if (sourceChild.Children.Count > 0)
            {
               //Move one level down
                currentSource = sourceChild;
                currentTarget = targetChild;
                depth++;
            }
        }
        else
        {
           //Move one level up
            if (depth == 0) break;
            depth--;
            currentSource = source;
            currentTarget = target;
            for (int i = 0; i < depth; i++)
            {
                int index = currentTarget.Children.Count - 1;
                currentSource = currentSource.Children[index];
                currentTarget = currentTarget.Children[index];
            }
        }
    }

    return target;
}

Faqat qiyin (va qisman samarasiz) qismi - yuqoriga ko'tarilgan qadamdir (shuning uchun umumiy yechim to'plamni talab qiladi). Ob'ektlarda ota-kod xususiyati bo'lsa, u oddiy bo'lar edi:

currentSource = currentSource.Parent;
currentTarget = currentTarget.Parent;

Bunday xususiyatlarning yo'qligi bilan ota-onalarni joriy manbalar va maqsadli narsalarni topish uchun biz ildiz buyumlaridan boshlaymiz va kerakli chuqurlikka urolmagunimizcha hozirgi vaqtda ishlov berish indeksidan pastga o'tamiz (qarang (3)).

2
qo'shib qo'ydi

Men hali ham katta hajmdagi suyakka daraxtning maksimal chuqurligi maqbul umumiy echim ekaniga ishonaman.

Qizig'i shundaki, ma'lumotlar strukturasi va konkret jarayoni faqat Children.Count ga asoslangan holda aylantirilishini aniqlashtirish uchun barcha zarur ma'lumotlarni o'z ichiga oladi. Nima kerakligini ko'rib chiqaylik:

(1) Are there more source children to process: source.Children.Count != target.Children.Count)

(2) Which is the next source child to process: source.Children[target.Children.Count]

(3) What is the current processing child index: target.Children.Count - 1

Yuqoridagi qoidalar qayta ishlash vaqtida har qanday darajaga nisbatan qo'llanishi mumkin.

Mana, amalga oshirish:

public static DestinationObject MapSourceToDestination(SourceObject source)
{
   //Map everything except childen
    Func primaryMap = s => new DestinationObject
    {
        Id = s.Id,
       //...
        Children = new List(s.Children.Count)//Empty list with specified capacity
    };

    var target = primaryMap(source);

    var currentSource = source;
    var currentTarget = target;
    int depth = 0;
    while (true)
    {
        if (currentTarget.Children.Count != currentSource.Children.Count)
        {
           //Process next child
            var sourceChild = currentSource.Children[currentTarget.Children.Count];
            var targetChild = primaryMap(sourceChild);
            currentTarget.Children.Add(targetChild);
            if (sourceChild.Children.Count > 0)
            {
               //Move one level down
                currentSource = sourceChild;
                currentTarget = targetChild;
                depth++;
            }
        }
        else
        {
           //Move one level up
            if (depth == 0) break;
            depth--;
            currentSource = source;
            currentTarget = target;
            for (int i = 0; i < depth; i++)
            {
                int index = currentTarget.Children.Count - 1;
                currentSource = currentSource.Children[index];
                currentTarget = currentTarget.Children[index];
            }
        }
    }

    return target;
}

Faqat qiyin (va qisman samarasiz) qismi - yuqoriga ko'tarilgan qadamdir (shuning uchun umumiy yechim to'plamni talab qiladi). Ob'ektlarda ota-kod xususiyati bo'lsa, u oddiy bo'lar edi:

currentSource = currentSource.Parent;
currentTarget = currentTarget.Parent;

Bunday xususiyatlarning yo'qligi bilan ota-onalarni joriy manbalar va maqsadli narsalarni topish uchun biz ildiz buyumlaridan boshlaymiz va kerakli chuqurlikka urolmagunimizcha hozirgi vaqtda ishlov berish indeksidan pastga o'tamiz (qarang (3)).

2
qo'shib qo'ydi

Men umuman iteratsiya ishlatadigan funktsiyasi o'z-o'zidan yaxshiroq deb o'ylamayman, lekin uni bir nechta kengaytmalar bilan qo'llayman

public static SourceObject GetAtList(this SourceObject s, List cycleRef)
{
    var ret = s;
    for (int i = 0; i < cycleRef.Count; i++)
    {
        ret = ret.Children[cycleRef[i]];
    }
    return ret;
}
public static void SetAtList(this DestinationObject d, List cycleRef, SourceObject s)
{
    var ret = d;
    for (int i = 0; i < cycleRef.Count - 1; i++)
    {
        ret = ret.Children[cycleRef[i]];
    }
    ret.Children.Add ( new DestinationObject() { Id = s.Id } );
}

va iteratorlar ro'yxatlari

public static DestinationObject MapSourceToDestinationIter(SourceObject source)
{
    var result = new DestinationObject();
    result.Id = source.Id;
    if (source.Children.Count == 0)
    {
        return result;
    }
    List cycleTot = new List();
    List cycleRef = new List();
    cycleRef.Add(0);
    cycleTot.Add(source.Children.Count-1);
    do
    {
        var curr = source.GetAtList(cycleRef);
        result.SetAtList(cycleRef, curr);
        if (curr.Children.Count == 0)
        {
            cycleRef[cycleRef.Count - 1]++;
            while (cycleRef[cycleRef.Count - 1]> cycleTot[cycleTot.Count-1])
            {
                cycleRef.RemoveAt(cycleRef.Count - 1);
                cycleTot.RemoveAt(cycleTot.Count - 1);
                if (cycleRef.Count == 0)
                {
                    break;
                }
                cycleRef[cycleRef.Count - 1]++;
            } 
        } else
        {
            cycleRef.Add(0);
            cycleTot.Add(curr.Children.Count - 1);
        }
    } while (cycleTot.Count>0);
    return result;
}

Men shu yo'l bilan borishni taklif qilmayman, ammo Linq muqobiliga qaraganda tezroq ...

Yaxshiyamki, Stack ning aniq ishlatilishi (Ivan Stoevning javobida kabi) maqbul echim.

1
qo'shib qo'ydi

Men umuman iteratsiya ishlatadigan funktsiyasi o'z-o'zidan yaxshiroq deb o'ylamayman, lekin uni bir nechta kengaytmalar bilan qo'llayman

public static SourceObject GetAtList(this SourceObject s, List cycleRef)
{
    var ret = s;
    for (int i = 0; i < cycleRef.Count; i++)
    {
        ret = ret.Children[cycleRef[i]];
    }
    return ret;
}
public static void SetAtList(this DestinationObject d, List cycleRef, SourceObject s)
{
    var ret = d;
    for (int i = 0; i < cycleRef.Count - 1; i++)
    {
        ret = ret.Children[cycleRef[i]];
    }
    ret.Children.Add ( new DestinationObject() { Id = s.Id } );
}

va iteratorlar ro'yxatlari

public static DestinationObject MapSourceToDestinationIter(SourceObject source)
{
    var result = new DestinationObject();
    result.Id = source.Id;
    if (source.Children.Count == 0)
    {
        return result;
    }
    List cycleTot = new List();
    List cycleRef = new List();
    cycleRef.Add(0);
    cycleTot.Add(source.Children.Count-1);
    do
    {
        var curr = source.GetAtList(cycleRef);
        result.SetAtList(cycleRef, curr);
        if (curr.Children.Count == 0)
        {
            cycleRef[cycleRef.Count - 1]++;
            while (cycleRef[cycleRef.Count - 1]> cycleTot[cycleTot.Count-1])
            {
                cycleRef.RemoveAt(cycleRef.Count - 1);
                cycleTot.RemoveAt(cycleTot.Count - 1);
                if (cycleRef.Count == 0)
                {
                    break;
                }
                cycleRef[cycleRef.Count - 1]++;
            } 
        } else
        {
            cycleRef.Add(0);
            cycleTot.Add(curr.Children.Count - 1);
        }
    } while (cycleTot.Count>0);
    return result;
}

Men shu yo'l bilan borishni taklif qilmayman, ammo Linq muqobiliga qaraganda tezroq ...

Yaxshiyamki, Stack ning aniq ishlatilishi (Ivan Stoevning javobida kabi) maqbul echim.

1
qo'shib qo'ydi

Yineleyicik funktsiyani faqatgina iteratsiyani ishlatadigan narsaga aylantirish mumkinmi?   manba obyekti grafigi ustida (ya'ni, recursionni olib tashlash va odatda, bir navbat/Stack foydalanish)?

LINQ.Uzunali chaqiruvni almashtirish. Yig'ma bilan tanlovni yig'ish va navbat bilan olish mumkin. Ota-ona tugunining identifikatorini eslab qolish uchun Tuple dan foydalanardim.

Ish vaqti - u (n). Space murakkabligi - u (bir darajadagi tugun soni).

Agar biz faqat navbat bilan foydalansak, kosmik murakkablikni o'zgartirishimiz mumkin - u (min (h * d, n)). h balandligi uchun, b tugundagi eng ko'p bolalar uchun. Ushbu kodni ko'rib chiqing:

public DestinationObject MapSourceToDestination(SourceObject root)
{
    Stack> stack = new Stack>();

    DestinationObject currentChild = new DestinationObject();
    currentChild.Id = root.Id;
    stack.Push(new Tuple(currentChild,root.Id));

    while(stack.Count > 0)
    {
        Tuple currentTuple = stack.Pop();

        current = currentTuple[0];

        children = current.Children;

        foreach (SourceObject sourceChild in root.Children)
        {
            currentChild = new DestinationObject();
            currentChild.Id = currentTuple[1];
            Children.Add(currentChild);
            stack.Push(new Tuple(currentChild,sourceChild.Id));
        }
    }
}
0
qo'shib qo'ydi

Yineleyicik funktsiyani faqatgina iteratsiyani ishlatadigan narsaga aylantirish mumkinmi?   manba obyekti grafigi ustida (ya'ni, recursionni olib tashlash va odatda, bir navbat/Stack foydalanish)?

LINQ.Uzunali chaqiruvni almashtirish. Yig'ma bilan tanlovni yig'ish va navbat bilan olish mumkin. Ota-ona tugunining identifikatorini eslab qolish uchun Tuple dan foydalanardim.

Ish vaqti - u (n). Space murakkabligi - u (bir darajadagi tugun soni).

Agar biz faqat navbat bilan foydalansak, kosmik murakkablikni o'zgartirishimiz mumkin - u (min (h * d, n)). h balandligi uchun, b tugundagi eng ko'p bolalar uchun. Ushbu kodni ko'rib chiqing:

public DestinationObject MapSourceToDestination(SourceObject root)
{
    Stack> stack = new Stack>();

    DestinationObject currentChild = new DestinationObject();
    currentChild.Id = root.Id;
    stack.Push(new Tuple(currentChild,root.Id));

    while(stack.Count > 0)
    {
        Tuple currentTuple = stack.Pop();

        current = currentTuple[0];

        children = current.Children;

        foreach (SourceObject sourceChild in root.Children)
        {
            currentChild = new DestinationObject();
            currentChild.Id = currentTuple[1];
            Children.Add(currentChild);
            stack.Push(new Tuple(currentChild,sourceChild.Id));
        }
    }
}
0
qo'shib qo'ydi

Sizning qarama-qarshi talablaringiz bor va shuning uchun sizning kodingiz kodda emas, balki talablarga/dizaynda bormi? Savolingizda eslatib o'tgan ikki nuqta uchun:

  1. You say that he number of children of a SourceObject is unknown until the run-time. In that case, the possibility of a stack overflow is unavoidable. That is what happens when the size of data is unknown and at run-time it turns out to be larger than the space available on the machine.

  2. Further, irrespective of your liking, a Stack or a Queue is the correct data structure for this kind of processing, if you want to avoid recursion. You have to either do recursion, or have to store your SourceObjects in some data structure to keep track of which one to visit as you continue the processing.

I would go with Stack/Queue method over recursion for graph exploration or graph traversal and stay aware of the fact that if the graph is big enough then my Stack/Queue will consume all the system memory, and cause an overflow.

Bunga yo'l qo'ymaslik uchun, mashinangizdagi xotirani oshiring (ya'ni kattalashtiring) yoki algoritmingizni bir vaqtning o'zida parallellashtirish (masalan, o'lchamlarini o'zgartirish) uchun sizning ishingizni bajaradigan mashinalarning sonini oshirish.

0
qo'shib qo'ydi

Sizning qarama-qarshi talablaringiz bor va shuning uchun sizning kodingiz kodda emas, balki talablarga/dizaynda bormi? Savolingizda eslatib o'tgan ikki nuqta uchun:

  1. You say that he number of children of a SourceObject is unknown until the run-time. In that case, the possibility of a stack overflow is unavoidable. That is what happens when the size of data is unknown and at run-time it turns out to be larger than the space available on the machine.

  2. Further, irrespective of your liking, a Stack or a Queue is the correct data structure for this kind of processing, if you want to avoid recursion. You have to either do recursion, or have to store your SourceObjects in some data structure to keep track of which one to visit as you continue the processing.

I would go with Stack/Queue method over recursion for graph exploration or graph traversal and stay aware of the fact that if the graph is big enough then my Stack/Queue will consume all the system memory, and cause an overflow.

Bunga yo'l qo'ymaslik uchun, mashinangizdagi xotirani oshiring (ya'ni kattalashtiring) yoki algoritmingizni bir vaqtning o'zida parallellashtirish (masalan, o'lchamlarini o'zgartirish) uchun sizning ishingizni bajaradigan mashinalarning sonini oshirish.

0
qo'shib qo'ydi