Колеги, качил съм ви домашното за "Ефективност на структурите от данни" от курса по "Структури от данни".
Задачите са насочени към развиване на умения за комбиниране на няколко структури от данни, за да се имплементира ефективно определена съвкупност от опрации върху някаква колекция от елементи.
Наков
Качил съм ви завършено лабораторното упражнение (лаб) по темата "ефективност на структурите от данни".
Упражнението е разписано много внимателно и подробно стъпка по стъпка и ви препоръчвам да го преминете, защото на изпита едната задача ще бъде подобна.
В упражнението се комбинират по нетривиален начин няколко структури от данни, за да се постигне добра производителност при имплементацията на структура от данни "колекция от хора". Всички операции са реализиране с константна или логаритмична сложност (ако изключим итерацията по намерените резултати).
Има старателно приготвени unit тестове и тестове за производителност. Времевото ограничение (timeout) за тестовете за прозиводителност е 4 пъти по-голяма от времето на моя лаптоп, но при много стара машина може да се наложи да ги промените.
Наков
Здравейте,
имам проблем с едната от задачите в това домашно, а именно при трета задача условието за "Find products by title + price range – returns the products sorted by id" имам проблем със сортирането по id. Ползвам
private Dictionary<string, OrderedDictionary<double, SortedSet<Product>>> productsByTitlePriceRange;
но след като върна резултат
public IEnumerable<Product> FindByTitlePriceRange(string title, int startPrice, int ednPrice)
{
var productsRange = this.productsByTitlePriceRange[title].Range(startPrice, true, ednPrice, true);
foreach (var products in productsRange)
{
foreach (var product in products.Value)
{
yield return product;
}
}
}
продуктите не са подредени по id ами по price. Това мие CompareTo метода
public int CompareTo(Product other)
{
return this.Id.CompareTo(other.Id);
}
Ето и линк с целия код на задачата: тук
Ще съм много благодарен, ако някой успее да реши проблема и да сподели, къде ми е грешката.
Има смисъл да се използва структура, която да държи вътрешно сортирани продуктите по Id, единсвено в случаите, когато нямаме обединяване на ключове, а случая е точно такъв.
SortedSet<Product> може да ти е просто Set<Products> - вече имаш константно включване, което е по-ефективно. Няма смисъл да пазиш тук елементите подредени.
Вместо yield return можеш да записваш резултата в променлива var products = new SortedSet<Product>() и накрая да е ретърнеш. Така ще имаш log N ако не броим foreach-a, което реално е голямото забавяне, но все пак би трябвало да е по-бързия вариант от позлзването на лист при много продукти.
Здрасти, Пешо ; )
С .Range метода връщаш няколко колекции, които са сортирани по Price (double ключа). Всяка от тях държи сет, сортиран по id. Mисля, че оттам ти идват тегобите : )
dim4o благодаря ти за предложенето решение. След като го направи стана и си работи добре, но все пак, не мога да си обясня, защо продуктите не ги връща сортирани по id, след като са във SortedSet<Product>, а ги връща сортирани по цена, след като в yield return достъпвам самия продукт.
Здравейте,
Пускам моите решения на домашното -> Домашно
Ако някой има съвети препоръки или каквото и да е - ще се радвам да го дискутираме.
Аз вървя малко назад с домашните и сега разгледах това на Dim4o. Мисля че не е коректно да се премахне productsByTitle.Remove(product.Title); по този начин, защото title не е уникално и по този начин ще се изтрият всички продукти с този title, а не само продукта с посоченото Id.
Абсолютно - трябваше да е _productsByTitle[product.Title].Remove(product);, аналогично на всички повтарящи се действия по-долу. Незнам защо съм го оставил така. Благодаря за забележката. В решението има и още една нередност. Ако Title == Supplier за два различни продукта например - може да стане мазало при тъсене с FindProductByTitleAndPriceRange или FindProductBySupplierAndPriceRange, защото за да пестя речници ги обединявам. Става въпрос за последните два речника. Ще ъпдейтна repository-то с коректното решение при първа възможност.
А как решихте проблема с Add метода, ако ID existevwa да го replacevate навсякъде?
@pafkuneca
Самата структура от данни Set прави това за нас. Тя гарантира уникалността на елементите и ако се опитваш да вкараш елемент с вече съществуващо Id то той се презаписва отгоре, понеже компаратора казава, че са еднакви (сравнимо по Id). В този смисъл това, което предложих по-горе за LinkedList няма да работи,защото ще трбва допълнителна логика и забавяне на програмата.
Благодаря ти, Димчо!Веднага ще опитам :)) и ще пиша какъв е резултата
Мисля, че има бъг.Ако добавя продукт1(1, "Lida", "Limonada", 5); и продукт3(1, "Lida", "Limonadaa", 3); Ами productsByTitle["Limonada"] все още съдържа продукта1. Тоз ми беше въпроса, ако не изтриваме productsByTitle от старото заглавие, старото заглавие още ще стои въпреки, че такъв елемент не би трябвало да съществува и стария елемент ще бъде в productsByTitle["Limonada"] :) ?
Аз например ползвам това при добавяне на 2 еднакви елемента.
Add("1", "Lida", "Limonada", 4);
Add("1", "Lida", "Limonadaa", 5);
Тук е малко порция от метода Add :)
string key = String.Empty;
foreach (var KVP in productsByTitle)
{
if (KVP.Value.Contains(product))
{
key = KVP.Key;
break;
}
}
if (key.Length > 0)
{
productsByTitle.Remove(key);
}
productsByTitle.EnsureKeyExists(title);
productsByTitle[product.Title].Add(product);
Здравейте,
Ето упражнението и на Java ТУК. Всички unit тестове минават, а тестовете за производителност отнемат повече време от това на Наков, но се вписват в допустимото. Приемам идеи за оптимизация.
Направи ми впечатление, че в C# тестовете "pepi@gmail.com" се очаква да е преди "pepi2@yahoo.fr" след сортитане по email. Но като сортитам същите стрингове в Java, те са наобратно.
Страхотно, благодаря за Java кода и тестовете. Включих го като линк към ресурсите към "Persons Collection" темата в архива с решението.
Наков