PDA

View Full Version : راهنمایی در خصوص حل یه الگوریتم ساده ولی جالب



moradian
چهارشنبه 03 تیر 1394, 00:29 صبح
سلام بر اساتید محترم
حقیقتش یه الگوریتم می خوام برا یه کار خاصی، خلاصه وار توضیح میدم:
ببینید فرض کنیم آرایه ای بسیار بزرگ از بایت داریم شامل اعداد 0 و 1 مثلا تو یه فایل که در ایندکس های نامشخص ولی پشت سر هم ذخیره شده اند. (در این مثال طول آرایه 2000 بایته) محتوای فایل:


11111111111111111111111111111111111111111111111111 11111111111111111111111111111111111111111111111100 00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000001111111111 11111111111111111111111111111111111111111111111111 11111111111111111111111111111111111111111111111111 11111111111111111111111111111111111111111111111111 11111111111111111111111111111111111100000000000000 00000000000111111111111111111111111111111111111111 11111111111111111111111111111111111111111111111111 11111111111111111111111111111111111111111111111000 00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000 00000000000000000001111111111111111111111111111111 11111111111111111111111111111111111111111111111111 11111111111111111111111111111111111111111111111111 11111111111111111111111111111111111111111111111111 11111111111111111111111111111000000000000000000000 00000000000000000000000000000000000000000000000000 00000000000000000000000000000000001111111111111111 11111111111111111111111111111111111111111111111111 11111111111111111111111111111111111111111111111111 11111111111111111111111111111111111111111111111111 11111111111111111111111111111111111111111111111111 11000000000000000000000000000000000000000000001111 11111111111111100000000000000000000000000000000000 00000000111111111111111111111111111111111111111111 11111111111111111111111111111111000000000000000000 00000000000000000000000000000000000000000000000000 00000000000000000000000000000000111111111111111111 11111111111111111111111111111111111000000000000111

لطفا این نمونه 0 و 1 ها رو کپی و فاصله ها رو حذف کنید و تو فایل جدیدی با نام bytes.txt تو فولدر Debug پروژه تون بریزید تا خروجی تون با من با اجرای کد یکسان بشه.
حال مساله اینجاست الگوریتمی میخوام که با کمترین تعداد اجرای بدنه حلقه، مثلا تعداد 1 ها را استخراج کند. خودم این کد رو فعلا نوشتم که هر چه بالا پایینش کردم خروجی صحیحی نگرفتم میدونم الگوریتم مزخرفیه!.


byte[] bytes = File.ReadAllBytes(Application.StartupPath + "\\bytes.txt");
int zero = bytes.Where(c => c == 48).Count();
int one = bytes.Where(c => c == 49).Count();
label4.Text = zero.ToString();
label5.Text = one.ToString();
int zCount = 0;
int oCount = 0;
int cloop = 0;
for (int i = 0; i < bytes.Length; i++)
{
cloop++;
bool b = bytes[i] == 49;
if (b)
{
oCount++;
}
else
{
while (!b)
{
if (bytes.Length - i < 10)
{
break;
}
i += 10;
b = bytes[i] == 49;
cloop++;
if (b)
{
i -= 9;
}
}
}
}
label6.Text = oCount.ToString();
label8.Text = cloop.ToString()+" of "+bytes.Length.ToString()+" ("+(cloop*100/bytes.Length).ToString()+"%)";

تصویر خروجی برنامه رو می بینید:
132560
از اساتید محترم خواهشمندم الگوریتم صحیحش رو برام زحمت بکشند.
ممنون

alireza264
چهارشنبه 03 تیر 1394, 00:47 صبح
سلام تصحیح کلمه خوبی نیست چون قطعه کدی که نوشتی خطا نداره بهتره بگیم بهینه کنیم
اما بنظرم بهتره الگوریتمو عوض کنی و به جای نوشتن رشته به صورت کامل اونو محدوده ای کنی روشش اینه که در خونه های زوج مقدار و در خونه های فرد تکرار بزاری

















132561
اینجوری تعداد خونه ها خیلی کمتر میشه

ali_md110
چهارشنبه 03 تیر 1394, 01:13 صبح
میتونید از لیست جنریک SortedDictionary که یک کلید و مقدار میگیره استفاده کنید

ابتدا یک کلاس بسازید



class CharCounter
{
public static SortedDictionary<char, ulong> Count(string stringToCount)
{
SortedDictionary<char, ulong> characterCount = new SortedDictionary<char, ulong>();

foreach (var character in stringToCount)
{
if (!characterCount.ContainsKey(character))
{
characterCount.Add(character, 1);
}
else
{
characterCount[character]++;
}
}

return characterCount;
}
}


بعدش بدین صورت استفاده کنید



string longText = Application.StartupPath + "\\bytes.txt";
var sr = new StreamReader(longText);
var count = CharCounter.Count(sr.ReadToEnd());

foreach (var character in count)
{
Console.WriteLine("{0} - {1}", character.Key, character.Value);
}

rahnema1
چهارشنبه 03 تیر 1394, 06:08 صبح
سلام
فکر کنم این روش سریعتر باشه

byte[] bytes = File.ReadAllBytes(Application.StartupPath + "\\bytes.txt");
uint[] hist = new uint[2];
for (int i = 0; i < bytes.Length; i++) {
++hist[bytes[i] - '0'];
}
label4.Text = hist[0].ToString();
label5.Text = hist[1].ToString();

moradian
چهارشنبه 03 تیر 1394, 08:34 صبح
با تشکر از کلیه دوستان برا وقتی که گذاشتین و پاسخ دادین.
عرض کنم اصلا مساله این نیست که بنده صفر و یک ها رو از تو یه فایل بخونم و تعداد یک هاشو بشمارم. عرض کردم فرض کنید. حالا مساله واقعی اینه:
در یه پوشه تو یه سایت اینترنتی تعداد بسیار زیادی (حدود یک میلیون) فایل تصویری داریم با نام های از 1.jpg تا 1000000.jpg که تقریبا پنجاه درصد اونها سایزشون زیر 20kb و بقیه بالاتر هست.
حالا بنده دقیقا میخوام تو یه حلقه بدون این که فایل های زیر 20kb را ابتدا دانلود و سپس سایزش رو مقایسه کنم و ذخیره کنم یانه کلا فایلا تا اونجایی که میشه دانلود نشن. چون می دونم همانند مثالی که در پست اولم گذاشتم بصورت مجتمع و در مقاطع مختلف فایل های زیر 20kb پشت سر هم هستند. همه راه های مثل سنجش هد فایل ها قبل از دانلود و ... رو هم امتحان کردم که کل فایل رو دانلود نکنم ولی ناگزیرم ابتدا کل فایل های ناخواسته رو دانلود کنم و در صورت احراز شرط مربوطه (بالای 20kb بودن) اونها رو ذخیره کنم که با این حساب تعداد فایل های مورد نیاز من 500 هزار تا فایله. که این کار مستلزم اولا وقت دوبرابری هست و ثانیا مصرف بیهوده ترافیک.
مطلبم طولانی شد. امیدوارم تونسته باشم لپ مطلب رو ادا کنم. جهت روشن شدن بهتر قضیه کدشو هم میگذارم:


for (int i = 0; i <= 1000000; i++)
{
Uri uri = new Uri(@"http://www.mysite.com/images/" + i.ToString() + ".jpg");
WebClient client = new WebClient();
byte[] data = client.DownloadData(uri);
bool b = data.Length > 20480;
if (b)
{
// save
passed++;
}
else
{
while (!b)
{
if (i > 999990)
{
break;
}
i += 10;
byte[] data = client.DownloadData(uri);
b = data.Length > 20480;
passed++;
if (b)
{
i -= 9;
}
}
}
}
lblPassed.Text = passed.ToString()+" of 1000000 ("+(passed*100/1000000).ToString()+"%)";

البته می دونم راه حل های بهتری برا این هدف وجود داره. دوستان ابتدا مطلب رو خوب درک کنن و سپس راه حل بدن یا حداقل همین کد رو بهینه کنیم تا به نتیجه برسیم.
ممنون از الطاف بیدریغ اساتید

moradian
چهارشنبه 03 تیر 1394, 11:33 صبح
اساتید محترم
راه حلی ندارید؟
ممنون میشم راهنمایی بفرمایید

rahnema1
چهارشنبه 03 تیر 1394, 13:44 عصر
بالاخره من نفهمیدم از صفر و یک چه طوری رسیدیم به سایز 20 کیلو بایت :قهقهه:
الان شما می خواهید فایلهای کمتر از 20 کیلوبایت را دانلود نکنید و فایلهای بیشتر از 20 کیلوبایت را کاملا دانلود کنید؟

اگه سرور اطلاعات مربوط به Content-Length را میده میتونید ابتدا سایز را به دست بیارید تا نخواهید دانلود کنید روشش هم در لینک زیر هست
http://stackoverflow.com/questions/122853/get-http-file-size
که اگه سرور دست خودتونه و این امکان را نداره شما واسش فعال کنید
یا نشه فعال کرد میتونید در سمت سرور یک اسکریپت بنویسید که لیست فایلهای کمتر از 20 برای شما تهیه کنه که مشکل ترافیک نداشته باشید
اگه دسترسی به سرور ندارید مجبورید ابتدا دانلود کنید تا سایز را به دست بیارید
اگه مشکل شما غیر از اینه لطفا سوال را واضح مطرح کنید

moradian
چهارشنبه 03 تیر 1394, 21:14 عصر
سلام دوست من، ممنون از همکاریتون


بالاخره من نفهمیدم از صفر و یک چه طوری رسیدیم به سایز 20 کیلو بایت :قهقهه:

در این خصوص گفتم شبیه سازی بشه که شما رو درگیر جزئیات دانلود و ... نکنم. فقط الگوریتم می خواستم


الان شما می خواهید فایلهای کمتر از 20 کیلوبایت را دانلود نکنید و فایلهای بیشتر از 20 کیلوبایت را کاملا دانلود کنید؟

بله دقیقا


اگه سرور اطلاعات مربوط به Content-Length را میده میتونید ابتدا سایز را به دست بیارید تا نخواهید دانلود کنید روشش هم در لینک زیر هست
http://stackoverflow.com/questions/122853/get-http-file-size
که اگه سرور دست خودتونه و این امکان را نداره شما واسش فعال کنید
یا نشه فعال کرد میتونید در سمت سرور یک اسکریپت بنویسید که لیست فایلهای کمتر از 20 برای شما تهیه کنه که مشکل ترافیک نداشته باشید

* سرور اطلاعات مربوط به Content-Length رو نمیده (منفی یک برمی گردونه)
* هیچگونه دسترسی به سرور ندارم (خارجیه)
* اسکریپتی در سمت سرور نمی تونم بنویسم


اگه دسترسی به سرور ندارید مجبورید ابتدا دانلود کنید تا سایز را به دست بیارید

دقیقا تنها راه اینکه مجبورم ابتدا دانلود کنم تا سایز را به دست بیارم


اگه مشکل شما غیر از اینه لطفا سوال را واضح مطرح کنید

در حالت طبیعی مشکلی نیست. فقط من میخوام با توجه به شرایطی که توضیح دادم الگوریتمی بنویسم تا میشه زیر 20kb دانلود نشن.
قبلا هم عرض کردم تنها شرایطی که هست اینه که بالا 20 ها و سپس زیر 20 ها در مقاطع مختلف پشت سر هم هستن (مثلا از 1.jpg تا 500.jpg بالا 20 هستن و از 501.jpg تا 580.jpg زیر 20 و مجددا از 581.jpg بالا 20 و الی آخر) امیدوارم متوجه شده باشید.
باز هم ممنون بخاطر پاسخهاتون

rahnema1
چهارشنبه 03 تیر 1394, 22:42 عصر
آها الان متوجه شدم
یه سوال آیا این مقطع هایی که گفتید می شه حداقلی برای طولشون مشخص کرد یا همین هم معلوم نیست؟ مثلا یک مقطع شامل 2 تا فایل باشه و یک مقطع دیگه شامل 100 تا فایل؟
اگه اندازه حداقل مقطع را بدونیم می شه جوری نوشت که مقداری بهینه تر بشه اما اگه اندازه حداقل مشخص نباشه ممکنه تعدادی فایلها از زیر دستتون در بره و دانلود نشه

moradian
چهارشنبه 03 تیر 1394, 23:22 عصر
آها الان متوجه شدم
یه سوال آیا این مقطع هایی که گفتید می شه حداقلی برای طولشون مشخص کرد یا همین هم معلوم نیست؟ مثلا یک مقطع شامل 2 تا فایل باشه و یک مقطع دیگه شامل 100 تا فایل؟
اگه اندازه حداقل مقطع را بدونیم می شه جوری نوشت که مقداری بهینه تر بشه اما اگه اندازه حداقل مشخص نباشه ممکنه تعدادی فایلها از زیر دستتون در بره و دانلود نشه
سلام مجدد
مشکل همین جاست همین هم معلوم نیست. البته حداقل برا طول مقاطع رو خودم بعدا اصلاح می کنم. می تونیم یه پارامتر step براش مشخص کنیم که تو متدمون به شکل پارامتریک از ما بگیره.
بازم ممنون

rahnema1
چهارشنبه 03 تیر 1394, 23:27 عصر
شما یه کاری کنید. یکی از این هاست های رایگان را بگیرید. با یه اسکریپت که در هاست رایگان میذارید تمام فایلهای بالای 20 را از اون سرور روی هاست دانلود کنید سپس از هاست رایگان به سیستم خودتون

moradian
چهارشنبه 03 تیر 1394, 23:33 عصر
فکر نمی کنم این کار رو بشه انجام داد. بعدشم مستقیم می خوام تو سیستم خودم بیاد چون بعد دانلود و قبل از ذخیره روش پروسس دارم.
تازه حدود یک میلیون فایله که هر کدوم میانگین 30 کیلو هم بشه ببین چقد میشه. هاست رایگانو می پکونه!

rahnema1
چهارشنبه 03 تیر 1394, 23:42 عصر
مستقیم از روی هاست رایگان به سیستم شما میاد
لینک زیر لیست بعضی هاست های رایگان هست بعضی ها هم ظاهرا فضای نامحدود میدن:
حالا بررسی کنید ضرر نداره
http://freehosting1.net/hosting.aspx?Search=True

rahnema1
پنج شنبه 04 تیر 1394, 00:03 صبح
حتی لازم نیست هاست رایگان فایلها را روی سیستمش ذخیره کنه. کافیه فقط لیست فایلهای بالای 20 را تهیه کنه

moradian
پنج شنبه 04 تیر 1394, 00:33 صبح
اکی، اگه لیست اونا رو هم تهیه کنه کفایت می کنه. ایده بسیار خوبیه.
در این صورت من خودم هاست دارم، لزومی به هاست رایگان نیست.
حالا بفرمایید این کار چه مزیتی داره؟ منظورتون اینه که سیستم من ساعت ها روشن نباشه و خود اسکریپت سمت سرور من این لیست رو پشت پرده تهیه کنه؟
درست فهمیدم؟ چون من تا حالا این کار رو نکردم.
میشه بیشتر توضیح بدین و برا مراحل کار و طریقه نوشتن اسکریپت راهنماییم کنین؟
ممنون میشم

rahnema1
پنج شنبه 04 تیر 1394, 11:00 صبح
چون نگرانی شما بابت ترافیک بود گفتم کار تهیه لیست را هاست رایگان برای شما انجام بده تا نگرانی بابت دانلود فایلهای اضافی نداشته باشید بعد شما لیست را از هاست دانلود کنید
این هم اسکریپت php


<?php
$file = "list.txt";
for($i = 0; $i < 1000000; $i++)
{
$basename = $i . ".jpg";
$url = "http://www.mysite.com/images/" . $basename ;
$file_size = stream_copy_to_stream (fopen($url, "rb"), fopen("php://memory", "wb"));
if ($file_size > 20000)
file_put_contents($file , $basename . "\r\n", FILE_APPEND);
}
?>