با سلام
البته چیزی ندیدم که پست دادم :
من یه ارایه دارم 262110 در 262110 از نوع صحیح که سیستم خطای
Exception of type 'System.OutOfMemoryException' was thrown.
میده بنظر چه را حلی وجود داره ؟ نمیتونم روی این پردازش انجام بدم مثلا از حالت اسپارس در بیارم چون بازم جستجوش برام هزینه زمان اجرا داره ؟ اگه ممکنه بگید چجوری میتونه ارایه ای یا چیزی شبیه ارایه با ساز بزرگ تعریف کنم ممنون
256 گیگابایت (تازه فقط برای نوع int) فضا میخوای؟!!!
دادشی اشتباه حساب کردی 127.9668 گیگ بایت ... هههنوشته شده توسط fjm11100
البته من سایز هر Int 2 بایت گرفتم طبق همون C ، تو سی شارپ نمیدونم .. درسته؟؟
hosh tabel بدردت نمیخوره؟
خیر.غلطه.میشه ۲۵۶ گیگ که دات نت ازش پشتیبانی نمیکنه میکنه(ref:پست mhsmity).مونو پشتیبانی میکنه.
۱.معمولا وقتی به این عددها میرسید دارید اشتباه میکنید.اول بگید چکار میخواهید بکنید.همیشه راه بهتری هم هست.
۲.زمان مورد میاز برای خوندن و نوشتن ۲۵۶ گیگ با یک ترد یه چیزی حدود نیم دقیقه میشه که فکر میکنم از هر sparseی بیشتره.
۳.اگر حجم اطلاعاتتون اینقدر زیاده پیشنهاد میکنم از همون c استفاده کنید.
۴.اگر اطلاعاتتون گرانولاریتی زیادی نداره میتونید ۲۵۶ گیگ allocate کنید ولی به یک bitmap هم نیاز دارید که بهتون بگه کدوم page ها رو zero کردید و کدومها رو نه.
۵.از MemoryMappedFile هم میتونی استفاده کنی.
حالا چیکار میخوای بکنی؟امیدوارم مشق استاد و پروژه نباشه.
آخرین ویرایش به وسیله FastCode : یک شنبه 24 شهریور 1392 در 16:17 عصر
بین کار شما رو راه می نداره
<gcAllowVeryLargeObjects> Element
MemoryMappedFile Class
سلام ممنون از پاسختون شاید بقول یکی از دوستان من از الگوریتم بهینه برای این کار استفاده نمی کنیم.
من یه گراف دارم که جهت داره و من با استفاده از اندیس های ارایه می خواستم همسایه های هر نود رو پیدا کنم یعنی هر نود با کدوم نود دیگه در ارتباطه که مشکل من هم تعداد نود های زیاد و این خطایی که طاهر میشه چه راه هایی وجود داره که بتونم نشنون بدم یه نود با چند تا نود دیگه در ارتباطه و اینکه از لحاظ حافظه ای با 263000 نود مشکلی پیدا نکنم .
در ضمن نمی خوام از فایل استفاده کنم که هزینه خوندن و نوشتن روی دیسک بپردازم . می خوام تو حافظه باشن و فقط بدونم یه نود با چه نودهای دیگه ای در ارتباطه .
در ضمن گراف من یه همچین ساختاری داره
1,2
1,3
1,4
1,5
2,3
3,4
مثال بالا نشون دهنده اینه که نود 1 درجه خروجیش 4 هستش و نود 2و3 در جه خروجیش 1 فقط تعداد اینا باز تاکید میکنم که زیادن .
مساله شما رو میشه با ۴ مگ حل کرد.نه ۲۵۶ گیگ.
اطلاعات مسالتون رو کامل بزارید.
نقدا یک راه به ذهنم رسید(فعلا نصفه شبه ببینم صبح چی میشه!)که حجم را به 8 گیگ برسونی.
فرض کن یک مربع 263000 در 263000 داریحالا هر خونه که سیاه بشه(یا بیت 1 باشه) میشه یک ارتباط مثلا اگه خونه ردیف 1 و ستون 100 یک باشه یعنی نود 1 و 100 به هم متصل هستند.
حالا ردیف به ردیف هر 8 تا خونه را یک بایت در نظر بگیر. میشه 263000 تقسیم به 8 یا 32875 بایت،
نتیجه این که تو 32875 در 263000 بایت حافظه لازم داری که تقریبا میشه 8 گیگ
البته فضاهای مربعی (مثل ردیف 1 ستون 1 یا ردیف 6 ستون 6 و یا ردیف 1003 ستون 1003) اضافه اند چون خود نود که به خودش وصل نیست و اگه بشه این فضاها را کم کرد که بهتر، همینطور وقتی مثلا 1 به 100 وصله دلیلی نداره وصل بودن 100 به 1 را هم حفظ کنیم(مربع گنده ما میشه مثلث قائم الزاویه و 8 گیگ میشه حدود 4 گیگ)
حالا برای اینکه ببینی 1 به چند تا نود وصله کافیه ببینی بایتهای ردیف اول در مجموع چند تا بیت 1 دارند. یا برای 263000 باید ببینی که بایتهای ردیف 263000 چندتا یک دارند!
مال من که بهتره.۴ مگ بدون false pasitive بعد از removeنقدا یک راه به ذهنم رسید(فعلا نصفه شبه ببینم صبح چی میشه!)که حجم را به 8 گیگ برسونی.
فرض کن یک مربع 263000 در 263000 داری
حالا ردیف به ردیف هر 8 تا خونه را یک بایت در نظر بگیر. میشه 263000 تقسیم به 8 یا 32875 بایت،
نتیجه این که تو 32875 در 263000 بایت حافظه لازم داری که تقریبا میشه 8 گیگ
البته فضاهای مربعی (مثل ردیف 1 ستون 1 یا ردیف 6 ستون 6 و یا ردیف 1003 ستون 1003) اضافه اند چون خود نود که به خودش وصل نیست و اگه بشه این فضاها را کم کرد که بهتر، همینطور وقتی مثلا 1 به 100 وصله دلیلی نداره وصل بودن 100 به 1 را هم حفظ کنیم(مربع گنده ما میشه مثلث قائم الزاویه و 8 گیگ میشه حدود 4 گیگ)
حالا برای اینکه ببینی 1 به چند تا نود وصله کافیه ببینی بایتهای ردیف اول در مجموع چند تا بیت 1 دارند. یا برای 263000 باید ببینی که بایتهای ردیف 263000 چندتا یک دارند!
روش شما چی بود؟
چی فکر میکنی؟ساده ترین روش ممکن.
مثلا این یک مدلشه که میتونه راحت multi-thread بشه و تعداد زیادی insert و remove همزمان relation یا node رو پشتیبانی کنه.
class Node : IComparable
{
int ID;
SrtodeSet<Node> ParentRelations;
SrtodeSet<Node> ChildRelations;
public int Compare(Node l, Node r) { }
}
متاسفانه جواب سوالم که گفتم کامل توضیح بدند رو ندادن.من الان نمیدونم چند تا ترد با اطلاعات کار میکنه.یا قراره مثلا با OpenCL ارتباط برقرار بشه یا نه؟اطلاعات ثابته یا تغییر میکنه.هر کدومش کلی روی سرعت تاثیر داره.این بدترین حاتشه.
شرمنده من نفهمیدم! الان چطوری رابطه نودها نگهداری میشه که بعد شمرده بشه؟
اینطوری:
SrtodeSet<Node> ParentRelations; SrtodeSet<Node> ChildRelations;
اینطوری هم شمرده میشه:
ChildRelations.Count
خب اینجا رابطه parent و child وجود نداره که اینجا هر نود میتونه به نود دیگه وصل بشه یعنی هر نود از یک تا به همه 262999 تا نود دیگه میتونه وصل باشه. با این حساب شما باید شماره نودهای متصل به هر نود را داشته باشی که میشه 263000 در 262999!
لازم نیست شماره نود های متصل رو داشته باشم.وقتی خود نود رو دارم.
اینطوری میتونم یک نود رو در حین کار عوض کنم.یا اطلاعات دیگه کنارش بزارم.میتونم نود ها رو با ۵ خط کد قفل SS2PL کنم و با چند تا ترد همزمان باهاش به شکل transactional کار کنم.
اگر تعداد رابطه های هر نود کمتر از 4 هزار تا باشه روش من به صرفه تره.در سیستم های ۶۴ بیت فکر میکنم میشه 3 هزار تا.(مطمئن نیستم.هر دو عدد رو ذهنی حساب کردم.ولی حدودا درسته)
آخرین ویرایش به وسیله FastCode : چهارشنبه 27 شهریور 1392 در 16:25 عصر
سلام علت تاخیر من عدم دسترسی به نت بود شرمنده :
مسله من خیلی ساده است فقط مشکل فضا دارم .ببینید من یه گراف جهت دار دارم حالا می خوام این گراف با تعداد نودهای زیاد رو تو کامپیوتر نمایش بدم درباره اینکه یکی از دوستان گفتند که شما می تونید یک طرف رابطه ذخیره کنید و بشه مثلث قائم الزوایه ما هیچ فرضی درباره اینکه گراف ما یال چندگانه داره یا نه و یا اینکه اگه نودی با نود دیگه در ارتباط عکسش صادق هست یا خیر نمیکنم چون گراف تعداد نودهاش زیاده .در ضمن من می خوام یه مکانیزمی معرفی کنید که بشه ازش براحتی برای جستجوی استفاده کرده . چون من می خوام از این گراف برای اجرای الگوریتمم در مقیاس زیاد استفاده کنم نه اینکه بیام فقط نمایش بدم .
۲۵۶ هزار تا نود دارید.
چند تا رابطه دارید؟به میلیارد میرسه یا نه؟روی هوا که نمیشه راه حل داد.باید یک مقدار مساله رو روشن تر کنید.یک ترد استفاده میکنید یا چند تا؟فقط از CPU استفاده میکنید یا پردازش MIMD هم دارید؟رابطه ها رو حذف هم میکنید یا نه؟اگر تعداد رابطه هاتون زیاد تر از چند میلیاد هست اشکالی نداره راه حلی بدیم که حداکثر تا 1.2 برابر اطلاعاتتون با هارد دیسک کار کنه؟آیا مسیر بین چند نود در الگوریتم شما تاثیر داره یا نودها دو به دو مقایسه میشوند؟دو طرف رابطه برای شما اهمیت دارد یا خیر؟
لطفا مسالتون رو کامل شرح بدید.
سلام ممنون از پاسختون :
Nodes: 262111 Edges: 1234877
بعدش اینکه رابطه ها رو می خوام چون برای جستجو از اونا استفاده می کنم . از یک ترد استفاده می کنم از یه CPU استفاده می کنم و من تو الگوریتمم نیاز دارم بررسی کنم که این هر نودی با چه نودهایی در ارتباطه . ممنون .
فقط یک میلیون؟من روی میلیارد حساب کرده بودم.این مساله نزدیک ۱۰ مگ حافظه میخواد.
sealed class node
{
public node(int id, node[] Collection)
{
this.Collection = collection;
this.id = id;
}
node[] Collection;
int id; public ID { get { return id; } }
list<node> refs = new List<node>();
void verify(node noderef)
{
if(noderef.Collection != Collection)
throw new InvalidOperationException("cross-collection reference detected.");
}
void verify (int nodeid)
{
if(nodeid >= Collection.Length)
throw new InvalidOperationException("cross-collection reference detected.there may be false negatives.");
}
public void AddRefSafe(node noderef)
{
lock(refs)
AddRef(noderef);
}
public void AddRef(node noderef)
{
if(noderef == this)
throw new Exception();
verify(noderef);
refs.Add(noderef);
}
public void ContainsRefSafe(node noderef)
{
lock(refs)
return ContainsRef(noderef);
}
public void ContainsRef(node noderef)
{
verify(noderef);
return refs.Contains(noderef);
}
public void ContainsSafe(int nodeid)
{
lock(refs)
return Contains(nodeid);
}
public void Contains(int nodeid)
{
verify(noderef);
for(int n = 0;n != refs.Count;n++)
{
if(refs[n].id == nodeid)
return true;
}
return false;
}
//todo:implement bloom-filter based CanSee for memory-cheaper lookups.
public bool CanSee(node noderef, bool Safe)
{
return CanSee(noderef, Safe, new byte[(Collection.Length + 7) >> 3]);
}
private bool CanSee(node noderef, bool Safe, byte[] bitmap)
{
if(Contains(noderef))
return true;
bitmap[id >> 3] |= 1 << (id & 7);
if(Safe)
System.Threading.Monitor.Enter(refs);
try
{
for(int n = 0;n != refs.Count;n++)
{
int rid = refs[n].id;
if(bitmap[rid >> 3] & (1 << (rid & 7)) == 0)
{
if(CanSee(noderef, Safe, bitmap))
return true;
}
}
}
finally
{
if(Safe)
System.Threading.Monitor.Exit(refs);
}
return false;
}
}
void main()
{
node[] nodes = new node[262111];
for(int n = 0;n < nodes.Length;n++)
{
nodes[n] = new node(n, nodes);
}
//fill data here
//test data here
}
edit:
CanSee یک مشکل داره که اول گره های مربوط درجه اول رو تست میکنه بعد علامت میزنه.توی حالت های ستاره ای یک مقدار سرعتش کم میشه.اگر خیلی سرعت کمه میتونی تغییرش بدی.احتمالا میشه تا ۱۰ ۲۰ درصد سریعترش کرد.
آخرین ویرایش به وسیله FastCode : چهارشنبه 27 شهریور 1392 در 17:49 عصر دلیل: sealed
با سلام
من یه همچین برنامه ای رو در مورد پیدا کردن کوتاه ترین راه برای رسیدن به گراف مقصد با کمترین هزینه .. نوشته بودمم. البته توی c پیشنهادی که میکنم اینکه برای هر راس حداکثر خروجی در نظر بگیر طبق اون در جدولی که طراحی میکنی فیلد در نظر بگیر و در هر فیلد از رکورد های یک راس مشخص کن با چه راس هایی دیگه در ارتباط هست .. طبق این روی جدولت انالیزهایی که میخوایی انجام بدی رو اعمال کن.
موفق باشی
اگر کوتاهترین مسیر رو میخواستن که میشد الگوریتم دکسترا رو بهشون معرفی کنیم.فکر نمیکنم منظورشون این بوده باشه.
قوانین ایجاد تاپیک در تالار
پاسخ با نقل قول