PDA

View Full Version : سوال: توالی کاوی



minaalamshahi
پنج شنبه 16 بهمن 1393, 12:10 عصر
من یه فایل تکست دارم که شامل توالی های مختلف از 4 حرف مثلا ABCD می باشد

می خوام وقتی N=1 قرار دادم در این فایل ،تمام تکرار های A,B,C,D را جدا جدا پیدا کنم.

وقتی N=2 شد ، تمام حالتهای زیر مجموعه 2 حرفی از این 4 حرف را سرچ کند ،مثلا تعداد تکرار های AB,AC,AD,BC,BD,DB,DC,....

و این روال تا N=50 ادامه یابد

مشکلی که وجود دارد اینست که پس از جستجو خیلی از زیر دنباله های تولید شده هیچ تکراری در فایل ما ندارد و این تعداد خیلی زیاد بوده ولی زمان زیادی از ما می برد و باعث طولانی شدن جستجو می شود

مثلا از زیر دنباله ACCCCCB,ADDDDDDDDBو.....هیچ تکراری یافت نشود.



راه پیشنهادی دوستان چی هست؟

Saman_12
پنج شنبه 16 بهمن 1393, 14:27 عصر
سلام.
اگر متن مورد نظر فقط همین توالی ها باشه میشه این کارو کرد :
جای اینکه اول حالت های ممکن رو تولید کنی بعد دنبالشون بگردی اول دنبالشون بگرد اگر بود اونوقت به عنوان یه حالت اظافه کن.
این رو سر همی نوشتم شاید درست نباشه :

private Dictionary<string, Int32> LookUpText(string text)
{
Dictionary<string, Int32> result = new Dictionary<string, Int32>();
List<string> preresult = new List<string>();


for (Int32 index = 0; index <= text.Length - 1; index++)
{
for (Int32 count = 1; count <= text.Length - index; count++)
{
for (Int32 k = index; k <= text.Length - count; k += count)
{
string substr = text.Substring(k, count);


if (preresult.Contains(substr) == false)
{
preresult.Add(substr);
}
}
}
}


foreach (string key in preresult)
{
Regex regex = new Regex(key);


result.Add(key, regex.Matches(text).Count);
}


return result;
}

rahnema1
پنج شنبه 16 بهمن 1393, 16:20 عصر
سلام
اینم یه رقم دیگه.البته از SortedDictionary هم میتونید استفاده کنید

Dictionary<string, int> Tavali(string inputStr, int N)
{
Dictionary<string, int> mydic = new Dictionary<string, int>();
for (int i = 0; i < inputStr.Length - N + 1; i++) {
string subs = inputStr.Substring(i, N);
if (mydic.ContainsKey(subs)) {
mydic[subs]++;
}
else {
mydic.Add(subs, 1);
}
}
return mydic;
}

minaalamshahi
پنج شنبه 16 بهمن 1393, 23:55 عصر
یک نفر به من استفاده از تابعای Regex.Matches
رو پیشنهاد داده.
برای من سرعت و بهینه بودن مهم هست.الگوریتم پس زمینه تابعهای Regex.Matches چی هست؟
نظرتون راجع به این توابع چیه؟



string contents = sr.ReadToEnd();
MatchCollection matches = Regex.Matches(contents, searchtext);
count = matches.Count;

minaalamshahi
جمعه 17 بهمن 1393, 00:02 صبح
[/const string a = "aa14505gbbv505;
int count = a.Where(c => c == 'a').Count()

;

؟؟؟؟؟؟؟

string s = "shahryari";
int b = s.IndexOfAny(new char[]{'g','b','c','d','m'});

minaalamshahi
چهارشنبه 29 بهمن 1393, 00:53 صبح
کسی در مورد توالی کاوی ژنها می تونه منو راهنمایی کنه؟

plus
چهارشنبه 29 بهمن 1393, 04:57 صبح
Regex، یک زبان منظم رو ارائه میده و البته کار شما رو راه نمیندازه چون شما همه حالت ها رو میخواین نه یک الگوی خاص رو. LINQ و ... هم کار خاصی جز کاهش Performance برای شما نمیکنه.

با چهار حرف A, B, C و D یک رشته با طول 50 کاراکتر، 4 بتوان 50 حالت داره یعنی بیشتر از 10 بتوان 30 حالت! بنابراین عملا شما نمیتونید تک تک توالی ها رو تولید کنید و بعد به دنبالشون بگردین.
همونطور که یکی از دوستان گفتن، شاید امکانش باشه که شما توالی های موجود در فایل مورد نظر رو بخونید و تعداد اونها رو محاسبه کنید، در یک Hashtable بگذارین و بعد هر توالی ای که میخواین رو تعدادش رو دارین. البته این در صورتی هست که تعداد توالی های موجود در فایل هم نجومی نباشه. برای نیاز کمتر به حافظه میتونید مقادیر رو بجای رشته به صورت باینری در Hashtable نگه دارین تا حافظه کمتری مورد نیاز باشه. مثلا برای تووالی به طول 1 با چهار حرف فقط 2 بیت لازمه نه یک کاراکتر (8 یا 16 بیت).
در واقع جواب شما پست شماره 3 هست که باید روش کار کنید و اگه لازم باشه بهینش کنید.

minaalamshahi
چهارشنبه 13 اسفند 1393, 19:07 عصر
میشه یه لینک خوب برای آموزش Dictionary بهم معرفی کنید.
سرچ کردم اما آموزش جامع میخوام.چ.ن برای پروزه است و میخوام کامل روش مسلط باشم
دیکشنری از یه پشته استفاده می کنه؟
منطق کارش چه الگوریتمی هست برای جستجو؟
ممنون

minaalamshahi
چهارشنبه 13 اسفند 1393, 19:44 عصر
Regex، یک زبان منظم رو ارائه میده و البته کار شما رو راه نمیندازه چون شما همه حالت ها رو میخواین نه یک الگوی خاص رو. LINQ و ... هم کار خاصی جز کاهش Performance برای شما نمیکنه.

با چهار حرف A, B, C و D یک رشته با طول 50 کاراکتر، 4 بتوان 50 حالت داره یعنی بیشتر از 10 بتوان 30 حالت! بنابراین عملا شما نمیتونید تک تک توالی ها رو تولید کنید و بعد به دنبالشون بگردین.
همونطور که یکی از دوستان گفتن، شاید امکانش باشه که شما توالی های موجود در فایل مورد نظر رو بخونید و تعداد اونها رو محاسبه کنید، در یک Hashtable بگذارین و بعد هر توالی ای که میخواین رو تعدادش رو دارین. البته این در صورتی هست که تعداد توالی های موجود در فایل هم نجومی نباشه. برای نیاز کمتر به حافظه میتونید مقادیر رو بجای رشته به صورت باینری در Hashtable نگه دارین تا حافظه کمتری مورد نیاز باشه. مثلا برای تووالی به طول 1 با چهار حرف فقط 2 بیت لازمه نه یک کاراکتر (8 یا 16 بیت).
در واقع جواب شما پست شماره 3 هست که باید روش کار کنید و اگه لازم باشه بهینش کنید.

شما گفتید شاید نیازی به تولید همه توالی ها نباشه و شاید امکانش باشه که توالی های موجود در فایل رو بخونید و اونها رو محاسبه کنید.این روش خیلی خوبه.اما چطوری؟

پیشنهاد شما برای دیکشنری برای سرعت و مقدار حافظه کم هست یا روش سرچش ؟چون گفتید جواب همون پست شماره 3 هست که باید روش کار بشه؟از چه لحاظ پیشنهاد شده؟
این پیشنهاد یکی دیگر از دوستان هست
1- فایل مذکور را به گونه ای سازمان دهی کنید. مثلا به ترتیب طول رشته و ... در این صورت مشخص است که برای هر رشته کدام قسمت فایل را باید جستجو کنید و این زمان جستجو را پایین می آورد.
2- الگوهایی که می خواهید جستجو کنید با آگاهی از مدل هایی که در فایل وجود دارد prune کنید. یعنی ایده ای پیدا کنید که قبل از جستجو بفهمید که این الگو در فایل وجود دارد یا نه و در صورتی که وجود ندارد جستجو انجام ندهید.


ممنونم

minaalamshahi
پنج شنبه 14 اسفند 1393, 10:41 صبح
یه مساله ای هست در مورد پیشنهاد شماره 2 در پست بالا
اگر من بخوام به جای تولید انواع مختلف توالی با 4 حرف acgt قبل از جستجو ، بیام و در خود فایل بررسی کنم که چه توالی های موجود هست و بیام اونها رو جستجو کنم
آیا راهی جز این که بیام به صورت زیر عمل کنم دارم؟
مثلا n=1
باید کل فایل پیمایش بشه از i=0 to lenghtfile
و هر بار که به تکرار رسیدیم یکی به کانتر n=1 اضافه بشه
و وقتی n=2 شد
بیام از اول فایل بخونم و هر بار دو یکی یکی رشته های به طول 2 رو بخونم و تعداد تکرارشون رو دربیارم

و الی اخر
آیا این راه منظورتون هست؟
و آیا این راه از پست شماره 3 سریعتره؟
و در ضمن اینکه پست 3 هم داره کل فایل رو هر بار پیمایش می کنه
آیا راهی هست که کل فایل هر بار پیمایش خطی نشه؟

rahnema1
پنج شنبه 14 اسفند 1393, 11:47 صبح
میگم من اگه جای شما بودم تا حالا برنامه را اجرا کرده بودم و داده ه را هم تحلیل کرده بودم :)
الان این روشها را اجرا کرده اید؟ حتی می تونید زمان سنج بذارید ببینید کدوم سریعتر اجرا میشه!

minaalamshahi
پنج شنبه 14 اسفند 1393, 12:16 عصر
بله من این روش ها رو امتحان کردم
من یه برنامه نوشتم توش با regex توالی هام رو و ژنهام رو پیدا کردم
با دیکشنری جستجوشون کردم
و میخوام این برنامه رو ارتقا میدم
دنبال یه روش هستم که این جستجوی خطی رو کم کنم
ومیخوام مفاهیم رو کامل متوجه بشم
میخوام بدونم Dictionary باIDictionary فرقش چیه؟

من تا حالا با اینها کار نکردم
پرسیدنشون مشکلی داره؟
زمان سنج برای چی؟
یعنی همه برای ارتقا کارشون زمان سنج میگیرن؟
من منظورتون رو نمیفهمم
هر کسی جای خودش هست
شما هیچ وقت نمی تونی جای من باشین
با معذرت لطفا از این پستها نگذارید

hamid_hr
پنج شنبه 14 اسفند 1393, 12:25 عصر
زمان سنج باید استفاه کنید ببینید در شرایط مساوی کدام روش سریعتر هست
البته من اینطوری استفاده میکنم از زمان سنج

rahnema1
پنج شنبه 14 اسفند 1393, 12:44 عصر
بله من این روش ها رو امتحان کردم
من یه برنامه نوشتم توش با regex توالی هام رو و ژنهام رو پیدا کردم
با دیکشنری جستجوشون کردم
و میخوام این برنامه رو ارتقا میدم
دنبال یه روش هستم که این جستجوی خطی رو کم کنم
ومیخوام مفاهیم رو کامل متوجه بشم
میخوام بدونم Dictionary باIDictionary فرقش چیه؟

من تا حالا با اینها کار نکردم
پرسیدنشون مشکلی داره؟
زمان سنج برای چی؟
یعنی همه برای ارتقا کارشون زمان سنج میگیرن؟
من منظورتون رو نمیفهمم
هر کسی جای خودش هست
شما هیچ وقت نمی تونی جای من باشین
با معذرت لطفا از این پستها نگذارید

ظاهرا منظور من را بد برداشت کردید. منظور من از اینکه زمان سنج اینه که یک کلاس در سی شارپ هست به نام System.Diagnostics.Stopwatch که مدت زمان اجرای یک برنامه را محاسبه می کنه
چند روش به شما پیشنهاد داده شد حالا نمیدونم شما اینها را امتحان کردید یا نه؟ باز یه سری سوال مطرح کردید و یک سری روش پیشنهاد دادید بدون اینکه نسبت به پستهای قبلی هیچ واکنشی نشون بدید خب میتونستید همین پیشنهادهای خودتون را پیاده سازی کنید و تایم بگیرید و با اونها مقایسه کنید فکر می کنم بهتره یا اینکه خودتون برید در زمینه توالی کاوی ژنها مطالعه کنید یا اینکه بعضی موارد فکر کنم توی تالار الگوریتم ها مطرح بشه احتمالا زودتر به نتیجه می رسید تا توی تالار برنامه نویسی سی شارپ مطرح کنید. در هر صورت اگه بی احترامی از طرف من نسبت به شما صورت گرفت از شما عذرخواهی می کنم موفق باشید