وحید نصیری وحید نصیری
مطالب
نحوه استفاده از افزونه Firebug برای دیباگ برنامه‌های ASP.NET مبتنی بر jQuery
هر از چندگاهی سؤال «این مثال jQuery رو نمی‌تونم اجرا یا باز سازی کنم» در این سایت یا سایت‌های مشابه تکرار می‌شوند. بنابراین بهتر است نحوه عیب یابی برنامه‌های ASP.NET مبتنی بر jQuery را یکبار با هم مرور کنیم. در اینجا، مثال تهیه یک Image Slider را که پیشتر در سایت مطرح شده است، به نحوی دیگر بررسی خواهیم کرد:
1) فراموش می‌کنیم تا اسکریپت اصلی jQuery را به درستی پیوست و مسیردهی کنیم.
2) مسیر Generic handler دیگری را ذکر می‌کنیم.
3) مسیرهای تصاویری را که Image slider باید نمایش دهد، کاملا بی‌ربط ذکر می‌کنیم.
4) خروجی JSON نامربوطی را بازگشت می‌دهیم.
5) یکبار هم یک استثنای عمدی دستی را در بین کدها قرار خواهیم داد.

و ... بعد سعی می‌کنیم با استفاده از Firebug عیوب فوق را یافته و اصلاح کنیم؛ تا به یک برنامه قابل اجرا برسیم.


معرفی برنامه‌ای که کار نمی‌کند!

یک برنامه ASP.NET Empty web application را آغاز کنید. سپس سه پوشه Scripts، Content و Images را به آن اضافه نمائید. در این پوشه‌ها، اسکریپت‌های نمایش دهنده تصاویر، Css آن و تصاویری که قرار است نمایش داده شوند، قرار می‌گیرند:


سپس یک فایل default.aspx و یک فایل OrbitHandler.ashx را نیز به پروژه با محتویات ذیل اضافه کنید: (در این دو فایل، 5 مورد مشکل ساز یاد شده لحاظ شده‌اند)
محتویات فایل OrbitHandler.ashx.cs مطابق کدهای ذیل است:
using System.Collections.Generic;
using System.IO;
using System.Web;
using System.Web.Script.Serialization;

namespace OrbitWebformsTest
{
    public class Picture
    {
        public string Title { set; get; }
        public string Path { set; get; }
    }

    public class OrbitHandler : IHttpHandler
    {
        IList<Picture> PicturesDataSource()
        {
            var results = new List<Picture>();
            var path = HttpContext.Current.Server.MapPath("~/Images");

            foreach (var item in Directory.GetFiles(path, "*.*"))
            {
                var name = Path.GetFileName(item);
                results.Add(new Picture
                {
                    Path = /*"Images/" + name*/ name,
                    Title = name
                });
            }

            return results;
        }

        public void ProcessRequest(HttpContext context)
        {
            var items = PicturesDataSource();
            var json = /*new JavaScriptSerializer().Serialize(items)*/ string.Empty;
            throw new InvalidDataException("همینطوری");
            context.Response.ContentType = "text/plain";
            context.Response.Write(json);
        }

        public bool IsReusable
        { 
            get { return false; } 
        }
    }
}
در اینجا جهت سهولت دموی برنامه (و همچنین امکان باز تولید آن توسط خوانندگان)، از بانک اطلاعاتی استفاده نشده و عمدا از یک لیست جنریک تشکیل شده در حافظه کمک گرفته شده است. تصاویر برنامه در پوشه Images واقع در ریشه سایت، قرار دارند. بنابراین توسط متد PicturesDataSource، فایل‌های این پوشه را یافته و مطابق ساختار کلاس Picture بازگشت می‌دهیم. نهایتا این اطلاعات به ظاهر قرار است با فرمت JSON بازگشت داده شوند تا بتوان نتیجه را توسط افزونه Orbit استفاده کرد.

همچنین کدهای صفحه ASPX ایی که قرار است (به ظاهر البته) از این Generic handler استفاده کند به نحو ذیل است:
<%@ Page Language="C#" AutoEventWireup="true" CodeBehind="default.aspx.cs" Inherits="OrbitWebformsTest._default" %>

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head runat="server">
    <title></title>
    <link href="Content/orbit-1.2.3.css" rel="stylesheet" type="text/css" />
    <script src="Script/jquery-1.5.1.min.js" type="text/javascript"></script>
    <script src="Scripts/jquery.orbit-1.2.3.min.js" type="text/javascript"></script>
</head>
<body>
    <form id="form1" runat="server">
    <div id="featured">
    </div>
    </form>
    <script type="text/javascript">
        $(function () {
            $.ajax({
                url: "Handler.ashx",
                contentType: "application/json; charset=utf-8",
                success: function (data) {
                    $.each(data, function (i, b) {
                        var str = '<img src="' + b.Path + '" alt="' + b.Title + '"/>';
                        $("#featured").append(str);
                    });
                    $('#featured').orbit();
                },
                dataType: "json"
            });
        });
    </script>
</body>
</html>
خوب! اگر پروژه را اجرا کنیم، کار نمی‌کند. یک مستطیل مشکی رنگ در کنار صفحه ظاهر شده و همین! حالا چکار باید کرد؟


مراحل عیب یابی برنامه‌ای که کار نمی‌کند!

ابتدا برنامه را در فایرفاکس باز کرده و سپس افزونه Firebug را با کلیک بر روی آیکن آن، بر روی سایت فعال می‌کنیم. سپس یکبار بر روی دکمه F5 کلیک کنید تا مجددا مراحل بارگذاری سایت تحت نظر افزونه Firebug فعال شده، طی شود.


اولین موردی که مشهود است، نمایش عدد 3، کنار آیکن فایرباگ می‌باشد. این عدد به معنای وجود خطاهای اسکریپتی در کدهای ما است.
برای مشاهده این خطاها، بر روی برگه Console آن کلیک کنید: 


بله. مشخص است که مسیر دهی فایل jquery-1.5.1.min.js صحیح نبوده و همین مساله سبب بروز خطاهای اسکریپتی گردیده است. برای اصلاح آن سطر زیر را در برنامه تغییر دهید:
 <script src="Scripts/jquery-1.5.1.min.js" type="text/javascript"></script>
پیشتر پوشه Script ذکر شده بود که باید تبدیل به Scripts شود.

مجددا دکمه F5 را فشرده و سایت را با تنظیمات جدید اجرا کنید. اینبار در برگه Console و یا در برگه شبکه فایرباگ، خطای یافت نشدن Generic handler نمایان می‌شوند:


برای رفع آن به فایل default.aspx مراجعه و بجای معرفی Handler.ashx، نام OrbitHandler.ashx را وارد کنید.
مجددا دکمه F5 را فشرده و سایت را با تنظیمات جدید اجرا کنید.


اگر به برگه کنسول دقت کنیم، بروز استثناء در کدها تشخیص داده شده و همچنین در برگه Response پاسخ دریافتی از سرور، جزئیات صفحه خطای بازگشتی از آن نیز قابل بررسی و مشاهده است.
اینبار به فایل OrbitHandler.ashx.cs مراجعه کرده و سطر throw new InvalidDataException را حذف می‌کنیم. در ادامه برنامه را کامپایل و مجددا اجرا خواهیم کرد.



با اجرای مجدد سایت، تبادل اطلاعات صحیحی با فایل OrbitHandler.ashx برقرار شده است، اما خروجی خاصی قابل مشاهده نیست. بنابراین بازهم سایت کار نمی‌کند.
برای رفع این مشکل، متد ProcessRequest را به نحو ذیل تغییر خواهیم داد:
        public void ProcessRequest(HttpContext context)
        {
            var items = PicturesDataSource();
            var json = new JavaScriptSerializer().Serialize(items);            
            context.Response.ContentType = "text/plain";
            context.Response.Write(json);
        }
برنامه را کامپایل کرده و اجرا می‌کنیم. برنامه اجرا می‌شود، اما باز هم کار نمی‌کند. مشکل از کجاست؟


بله. تمام تنظیمات به نظر درست هستند، اما در برگه شبکه فایرباگ تعدادی خطای 404 و یا «یافت نشد»، مشاهده می‌شوند. مشکل اینجا است که مسیرهای بازگشت داده شده توسط متد Directory.GetFiles، مسیرهای مطلقی هستند؛ مانند c:\path\images\01.jpg و جهت نمایش در یک وب سایت مناسب نمی‌باشند. برای تبدیل آن‌ها به مسیرهای نسبی، اینبار کدهای متد تهیه منبع داده را به نحو ذیل ویرایش می‌کنیم:
        IList<Picture> PicturesDataSource()
        {
            var results = new List<Picture>();
            var path = HttpContext.Current.Server.MapPath("~/Images");

            foreach (var item in Directory.GetFiles(path, "*.*"))
            {
                var name = Path.GetFileName(item);
                results.Add(new Picture
                {
                    Path = "Images/" + name,
                    Title = name
                });
            }

            return results;
        }
در این کدها فقط قسمت Path ویرایش شده است تا به مسیر پوشه Images واقع در ریشه سایت اشاره کند.
اینبار اگر برنامه را اجرا کنیم، بدون مشکل کار خواهد کرد.

بنابراین در اینجا مشاهده کردیم که اگر «برنامه‌ای مبتنی بر jQuery کار نمی‌کند»، چگونه باید قدم به قدم با استفاده از فایرباگ و امکانات آن، به خطاهایی که گزارش می‌دهد و یا مسیرهایی را که یافت نشد بیان می‌کند، دقت کرد تا بتوان برنامه را عیب یابی نمود.


سؤال مهم: اجرای کدهای jQuery Ajax فوق، چه تغییری را در صفحه سبب می‌شوند؟

اگر به برگه اسکریپت‌ها در کنسول فایرباگ مراجعه کنیم، امکان قرار دادن breakpoint بر روی سطرهای کدهای جاوا اسکریپتی نمایش داده شده نیز وجود دارد:


در اینجا همانند VS.NET می‌توان برنامه را در مرورگر اجرا کرده و تگ‌های تصویر پویای تولید شده را پیش از اضافه شدن به صفحه، مرحله به مرحله بررسی کرد. به این ترتیب بهتر می‌توان دریافت که آیا src بازگشت داده شده از سرور فرمت صحیحی دارد یا خیر و آیا به محل مناسبی اشاره می‌کند یا نه. همچنین در برگه HTML آن، عناصر پویای اضافه شده به صفحه نیز بهتر مشخص هستند:

‫۱۱ سال و ۶ ماه قبل، چهارشنبه ۴ اردیبهشت ۱۳۹۲، ساعت ۱۷:۰۰
محمد خورسندی محمد خورسندی
نظرات مطالب
تفاوت‌های Stored Procedure و Function ها در SQL Server
در Functionها فقط میتوان از table variableها استفاده کرد ولی در SPها هم میتوان  از Temp tableها و هم از table variableها استفاده کرد.
functionها را میتوان در Join استفاده کرد ولی SP‌ها این قابلیت را ندارند(شاید مورد ۴)
‫۹ سال و ۸ ماه قبل، چهارشنبه ۲۰ اسفند ۱۳۹۳، ساعت ۰۲:۵۱
علی یگانه مقدم علی یگانه مقدم
مطالب
درخت‌ها و گراف قسمت چهارم
در قسمت قبلی مبحث پیاده سازی ساختمان (ساختار) درخت‌های جستجوی دودویی را به پایان رساندیم. در این قسمت قرار است بر روی درخت متوازن بحث کنیم و آن را پیاده سازی نماییم.

درخت متوازن
همانطور که دیدید، عملیات جستجو  روی درخت جستجوی دو دویی به مراتب راحت و آسان‌تر است؛ ولی با این حال این درخت در عملیاتی چون درج و حذف، یک نقص فنی دارد و آن هم این است که نمی‌تواند عمق خود را کنترل کند و همینطور به سمت عمق‌های بیشتر و بزرگتر حرکت می‌کند. مثلا ساختار ترتیبی زیر را برای مقداری‌های 1 و 2 و 3 و 4 و  5و 6 در نظر بگیرید:

در این حالت دیگر درخت مانند یک درخت رفتار نمی‌کند و بیشتر شبیه لیست پیوندی است و عملیات جستجو همینطور کندتر و کندتر می‌شود و دیگر مثل سابق نخواهد بود، پیچیدگی برنامه بیشتر خواهد شد و از (Log(n به n می‌رسد. از آنجا که دوست داریم برای عملیات‌های رایجی چون درج و جستجو و حذف، همین پیچیدگی لگاریتمی را حفظ کنیم، از ساختاری جدیدتر بهره خواهیم برد.

درخت دودویی متوازن:  درختی است که در آن هیچ برگی، عمقش از هیچ برگی بیشتر نیست.

درخت دودویی متوازن کامل: درختی که تفاوتش در تعداد گره‌های چپ یا راست است و حداقل یک فرزند دارند.

درخت دودویی متوازن حتی اگر کامل هم نباشد، در عملیات پایه‌ای چون افزودن، حذف و جستجو در بدترین حالت هم با پیچیدگی لگاریتمی تعداد گام‌ها همراه است. برای اینکه این درخت با به هم ریختگی توازنش روبرو نشود، باید حین انجام عملیات پایه، جایگاه تعداد المان‌های آن بررسی و اصلاح شود که به این عملیات چرخش یا دوران Rotation می‌گویند. انجام این عملیات بستگی دارد که پیاده سازی این درخت به چه شکلی باشد و به چه صورتی پیاده سازی شده باشد. از پیاده سازی‌های این درخت می‌توان به درخت سرخ-سیاه Black Red Tree ، ای وی ال AVL Tree ، اسپلی Splay و ... اشاره کرد.

با توجه به موارد بالا میتوانیم به نتایج زیر برسیم که چرا این درخت در هر حالت، پیچیدگی زمانی خودش را در لگاریتم n حفظ می‌کند:

  • المان‌ها و عناصرش را مرتب شده نگه می‌دارد.
  • خودش را متوازن نگه داشته و اجازه نمی‌دهد عمقش بیشتر از لگاریتم n شود.

نمونه ای از درخت جستجوی دو دویی

همان درخت ولی به صورت متوازن با پیاده سازی AVL


درخت‌های متوازن هم می‌متوانند دو دویی یا باینری باشند و هم غیر باینری non-Binary

درخت‌های دو دویی در انجام عملیات بسیار سریع هستند و در بالا به تعدادی از انواع پیاده سازی‌های آن اشاره کردیم.

درخت‌های غیر باینری نیز مرتب و متوازن بوده، ولی می‌توانند بیش از یک کلید داشته باشند و همچنین بیشتر از دو فرزند. این درخت‌ها نیز عملیات خود را بسیار سریع انجام می‌دهند. از نمونه‌های این درخت می‌توان به B Tree,B+ Tree,Interval Tree اشاره کرد.

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

در خود دات نت در فضای نام system.collection.generic کلاس TreeSet یک نوع پیاده سازی از این درخت است که این پیاده سازی از نوع درخت سرخ سیاه می‌باشد و جالب است بدانید، در طی بیست گام می‌تواند در یک میلیون آیتم به جستجو بپردازد ولی خبر بد اینکه استفاده مستقیم از این کلاس ممکن نیست چرا که این کلاس به صورت داخلی internal برای استفاده‌ی خود کتابخانه طراحی شده است ولی خبر خوب اینکه کلاس sortedDictionary از این کلاس بهره برده است و به صورت عمومی در دسترس ما قرار گرفته است. همچنین کلاس SortedSet هم از دات نت 4  نیز در دسترس است.

 

کتابخانه‌های خارجی جهت استفاده در دات نت که به پیاده‌سازی درخت‌های متوازن پرداخته‌اند:

پیاده سازی Splay Tree با سی شارپ 

پیاده سازی AVL به صورت بهینه و آسان برای استفاده

پیاده سازی درخت AVL با کارایی بالا

پیاده سازی درخت AVL به همراه نمایش گرافیکی آن

درخت سرخ-سیاه

کتابخانه ای متن باز برای درخت سرخ-سیاه

درخت متوازن به همراه جست و جو و حذف و پیمایش ها

غیر دودویی‌ها

پیاده سازی B Tree

پیاده سازی Interval Tree 
پیاده سازی Interval Tree در سی ++  
‫۹ سال و ۸ ماه قبل، چهارشنبه ۶ اسفند ۱۳۹۳، ساعت ۰۴:۳۰
عثمان رحیمی عثمان رحیمی
مطالب
کپی کردن ساختار و داده‌های یک جدول از یک دیتابیس به دیتابیسی دیگر
در مواقعی ممکن است نیاز داشته باشیم که جدول یا جدول‌هایی از یک پایگاه داده را به یک پایگاه داده دیگر انتقال دهیم. در این مقاله قصد داریم روند انجام این کار را هم به صورت کوئری و هم به صورت ویزارد(گرافیکی) انجام دهیم.

برای شروع کار ابتدا دو دیتابیس به اسم‌های databasefrm و databaseto می‌سازیم. دیتابیس databasefrm شامل یک جدول به اسم emp با سه فیلد ID,Name,Address می‌باشد. قصد داریم جدول tmp از دیتابیس databasefrm را به دیتابیس databaseto انتقال دهیم. برای انجام این کار، یکی از روش‌های زیر را استفاده خواهیم کرد:

روش 1 : استفاده از کوئری
ساختار کلی انجام این عمل به صورت زیر خواهد بود:
Select * into DestinationDB.dbo.tableName from SourceDB.dbo.SourceTable
مثال :
select * into databaseto.dbo.emp from databasefrm.dbo.Emp
با اجرای دستور فوق یک کپی از جدول emp به همراه تمامی داده‌های آن به دیتابیس databaseto منتقل و ایجاد می‌شوند. اگر بخواهیم تمامی ایندکس‌ها، تریگر‌ها و قید‌ها (Constraint) نیز منتقل شوند، برای اینکار نیاز به تولید یک اسکریپت خواهد بود (در ادامه).

حال اگر بخواهیم یک کپی از  جدول را در دیتابیس جاری ایجاد کنیم، ساختار آن به صورت زیر خواهد بود  :
select * into newtable from SourceTable
که نمونه ای از آن برای دیتابیس ما به صورت زیرخواهد بود :
 select * into  emp1 from emp

می‌توانیم فقط فیلدهایی مشخص را به جدول دیگر کپی کنیم. برای انجا این کار کافیست به جای *  اسم فیلد‌های مورد نیاز را نوشت که ساختار دستوری آن به صورت زیر است :
select col1, col2 into <destination_table> from <source_table>
که برای مثال ما به صورت زیر خواهد بود :
select Id,Name into databaseto.dbo.emp1 from databasefrm.dbo.Emp

بعد از اجرای کوئری فوق نتیجه به صورت زیر خواهد بود :

کد فوق باعث کپی کردن فیلد‌های Id,Name شده است.

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

select *into <destination_database.dbo.destination table> from _
<source_database.dbo.source table> where 1 = 2
که نمونه ای از آن برای مثال ما به صورت زیر خواهد بود :
select * into databaseto.dbo.emp from 
databasefrm.dbo.emp where 1 = 2
کاربرد where در دستور فوق برای این است که عنوان فیلد‌ها را بگیریم و در جدول دیگری ذخیره کنیم.

نکته: هر وقت نیاز بود که فقط فیلد‌های یک جدول را دریافت کنید، می‌تواند از کدی همانند فوق استفاده کنید؛ با یک شرط که همیشه false برگرداند. ولی راه بهتری که توصیه میکنم استفاده از Top در دستور  Select می‌باشد. نمونه‌ای از دستور فوق:
select top(0) * into databaseto.dbo.emp from 
databasefrm.dbo.emp
همانطور که مشاهده می‌کنید دیگر در دستور فوق خبری از where نیست.

روش 2: ویزارد

جهت تهیه کارهای فوق به صورت ویزارد، به صورت خلاصه فقط به روند انجام کار بسنده می‌کنیم:
1- SSMS را باز کنید.
2- بر روی دیتابیس مورد نظر کلیک راست کرده و از منوی ظاهر شده Task را انتخاب نموده و در کادر بازشو Export data را انتخاب کنید.
3- در پنجره‌ی ظاهر شده بر روی دکمه next کلیک کرده و در پنجره بعدی، نوع اعتبار سنجی را انتخاب کرده و دیتابیس مورد نظر را انتخاب نمایید (databasefrm).
4- همانند مرحله 3 است با این تفاوت که اینبار دیتابیس مقصد را انتخاب می‌کنیم (databaseto).
5- در پنجره‌ی بعدی گزینه اول را انتخاب کرده (copy data from ...) و بعد از کلیک بر روی next در پنجره ظاهر شده، جدول یا جداول مورد نظر را انتخاب کنید.

روش 3 : تولید اسکریپت
 
با استفاده از دو روش فوق فقط می‌توانستیم ساختار جداول و داده‌های آن را انتقال بدهیم. برای انتقال کامل جداول مثل تریگرها، قیدها و ... می‌بایست از جدول یا جداول اسکریپت تولید و در نهایست اسکریپت را اجرا نماییم.
Right click on datbase >>Task>>Generate script>>next

انتخاب دیتابیس مورد نظر و بعد انتخاب مواردی که قصد داریم از آنها اسکریپت ایجاد کنیم و در پایان اسکریپت مورد نظر را بر روی دیتابیس مقصد (databaseto) اجرا می‌کنیم.
و در پایان نهایت تشکر را از تمام عزیزان و دوستان نویسنده‌ی سایت دارم. امیدوارم در سال 94 شاهد موفقیت‌های خوبی در حوزه‌ی نرم افزار باشیم.
‫۹ سال و ۷ ماه قبل، پنجشنبه ۲۸ اسفند ۱۳۹۳، ساعت ۰۳:۵۵
علی یگانه مقدم علی یگانه مقدم
مطالب
ساختار داده‌های خطی Linear Data Structure قسمت اول
بعضی از داده‌ها ساختارهای ساده‌ای دارند و به صورت یک صف یا یک نوار ضبط به ترتیب پشت سر هم قرار می‌گیرند؛ مثل ساختاری که صفحات یک کتاب را نگهداری می‌کند. یکی از نمونه‌های این ساختارها، List، صف، پشته و مشتقات آن‌ها می‌باشند.

ساختار داده‌ها چیست؟
در اغلب اوقات، موقعی‌که ما برنامه‌ای را می‌نویسیم با اشیاء یا داده‌های زیادی سر و کار داریم که گاهی اوقات اجزایی را به آن‌ها اضافه یا حذف می‌کنیم و در بعضی اوقات هم آن‌ها را مرتب سازی کرده یا اینکه پردازش دیگری را روی آن‌ها انجام میدهیم. به همین دلیل بر اساس کاری که قرار است انجام دهیم، باید داده‌ها را به روش‌های مختلفی ذخیره و نگه داری کنیم و در اکثر این روش‌ها داده‌ها به صورت منظم و پشت سر هم در یک ساختار قرار می‌گیرند.
ما در این مقاله، مجموعه‌ای از داده‌ها را در قالب ساختارهای متفاوتی بر اساس منطق و قوانین ریاضیات مدیریت می‌کنیم و بدیهی است که انتخاب یک ساختار مناسب برای هرکاری موجب افزایش کارآیی و کارآمدی برنامه خواهد گشت. می‌توانیم در مقدار حافظه‌ی مصرفی و زمان، صرفه جویی کنیم و حتی گاهی تعداد خطوط کدنویسی را کاهش دهیم.

نوع داده انتزاعی Abstraction Data Type -ADT
به زبان خیلی ساده لایه انتزاعی به ما تنها یک تعریف از ساختار مشخص شده‌ای را می‌دهد و هیچگونه پیاده سازی در آن وجود ندارد. برای مثال در لایه انتزاعی، تنها خصوصیت و عملگر‌ها و ... مشخص می‌شوند. ولی کد آن‌ها را پیاده سازی نمی‌کنیم و این باعث می‌شود که از روی این لایه بتوانیم پیاده سازی‌های متفاوت و کارآیی‌های مختلفی را ایجاد کنیم.
ساختار داده‌های مختلف در برنامه نویسی:
  • خطی یا Linear: شامل ساختارهایی چون لیست و صف و پشته است: List ,Queue,Stack
  • درختی یا Tree-Like: درخت باینری ، درخت متوازن و B-Trees
  • Dictionary : شامل یک جفت کلید و مقدار است در جدول هش
  • بقیه: گراف‌ها، صف الویت، bags, Multi bags, multi sets
در این مقاله تنها ساختارهای خطی را دنبال می‌کنیم و در آینده ساختارهای پیچیده‌تری را نیز بررسی خواهیم کرد و نیاز است بررسی کنیم کی و چگونه باید از آن‌ها استفاده کنیم.
ساختارهای لیستی از محبوبترین و پراستفاده‌ترین ساختارها هستند که با اشیاء زیادی در دنیای واقعی سازگاری دارند. مثال زیر را در نظر بگیرید:
قرار است که ما از فروشگاهی خرید کنیم و هر کدام از اجناس (المان‌ها) فروشگاه را که در سبد قرار دهیم، نام آن‌ها در یک لیست ثبت خواهد شد و اگر دیگر المان یا جنسی را از سبد بیرون بگذاریم، از لیست خط خواهد خورد.
همان که گفتیم یک ADT میتواند ساختارهای متفاوتی را پیاده سازی کند. یکی از این ساختارها اینترفیس system.collection.IList است که پیاده سازی آن منجر به ایجاد یک کلاس جدید در سیستم دات نت خواهد شد. پیاده سازی اینترفیس‌ها در سی شارپ، قوانین و قرادادهای خاص خودش را دارد و این قوانین شامل مجموعه‌ای از متد‌ها و خصوصیت‌هاست. برای پیاده سازی هر کلاسی از این اینترفیس‌ها باید این متدها و خصوصیت‌ها را هم در آن پیاده کرد.
با ارث بری از اینترفیس system.collection.IList باید رابط‌های زیر در آن پیاده سازی گردد:
(void Add(object    افزودن المان به آخر لیست 
(void Remove(object   حذف یک المان خاص از لیست  
 ()void Clear    حذف کلیه المان‌ها
( bool Contains(object   شامل این داده میشود یا خیر؟
( void RemoveAt(int  حذف یک المان بر اساس  جایگاه یا اندیسش 
(void Insert(int, object
 افزودن یک المان در جایگاهی (اندیس) خاص بر اساس مقدار position 
(int IndexOf(object اندیس یا جایگاه یک عنصر را بر می‌گرداند
 [this[int ایندکسر ، برای دستریس به عنصر در اندیس مورد نظر

لیست‌های ایستا static Lists
آرایه‌ها می‌توانند بسیاری از خصوصیات ADT را پیاده کنند ولی تفاوت بسیار مهم و بزرگی با آن‌ها دارند و آن این است که لیست به شما اجازه می‌دهد به هر تعدادی که خواستید، المان‌های جدیدی را به آن اضافه کنید؛ ولی یک آرایه دارای اندازه‌ی ثابت Fix است. البته این نکته قابل تامل است که پیاده سازی لیست با آرایه‌ها نیز ممکن است و باید به طور خودکار طول آرایه را افزایش دهید. دقیقا همان اتفاقی که برای stringbuilder در این مقاله توضیح دادیم رخ می‌دهد. به این نوع لیست‌ها، لیست‌های ایستایی که به صورت آرایه ای توسعه پذیر پیاده سازی میشوند می‌گویند. کد زیر پیاده سازی چنین لیستی است:
public class CustomArrayList<T>
{
    private T[] arr;
    private int count;
 
    public int Count
    {
        get
        {
            return this.count;
        }
    }
 
    private const int INITIAL_CAPACITY = 4;
 
    public CustomArrayList(int capacity = INITIAL_CAPACITY)
    {
        this.arr = new T[capacity];
        this.count = 0;
    }
در کد بالا یک آرایه با طول متغیر INITIAL_CAPACITY که پیش فرض آن را 4 گذاشته ایم می‌سازیم و از متغیر count برای حفظ تعداد عناصر آرایه استفاده می‌کنیم و اگر حین افزودن المان جدید باشیم و count بزرگتر از INITIAL_CAPACITY رسیده باشد، باید طول آرایه افزایش پیدا کند که کد زیر نحوه‌ی افزودن المان جدید را نشان می‌دهد. استفاده از حرف T بزرگ مربوط به مباحث Generic هست. به این معنی که المان ورودی می‌تواند هر نوع داده‌ای باشد و در آرایه ذخیره شود.
public void Add(T item)
{
    GrowIfArrIsFull();
    this.arr[this.count] = item;
    this.count++;
} 

public void Insert(int index, T item)
{
    if (index > this.count || index < 0)
    {
        throw new IndexOutOfRangeException(
            "Invalid index: " + index);
    }
    GrowIfArrIsFull();
    Array.Copy(this.arr, index,
        this.arr, index + 1, this.count - index);
    this.arr[index] = item;
    this.count++;
} 

private void GrowIfArrIsFull()
{
    if (this.count + 1 > this.arr.Length)
    {
        T[] extendedArr = new T[this.arr.Length * 2];
        Array.Copy(this.arr, extendedArr, this.count);
        this.arr = extendedArr;
    }
}
 
public void Clear()
{
    this.arr = new T[INITIAL_CAPACITY];
    this.count = 0;
}
در متد Add خط اول با تابع GrowIfArrIsFull بررسی می‌کند آیا خانه‌های آرایه کم آمده است یا خیر؟ اگر جواب مثبت باشد، طول آرایه را دو برابر طول فعلی‌اش افزایش می‌دهد و خط دوم المان جدیدی را در اولین خانه‌ی جدید اضافه شده قرار می‌دهد. همانطور که می‌دانید مقدار count همیشه یکی بیشتر از آخرین اندیس است. پس به این ترتیب مقدار count همیشه به  خانه‌ی بعدی اشاره می‌کند و سپس مقدار count به روز میشود. متد دیگری که در کد بالا وجود دارد insert است که المان جدیدی را در اندیس داده شده قرار می‌دهد. جهت این کار از سومین سازنده‌ی array.copy استفاده می‌کنیم. برای این کار آرایه مبدا و مقصد را یکی در نظر می‌گیریم و از اندیس داده شده به بعد در آرایه فعلی، یک کپی تهیه کرده و در خانه‌ی بعد اندیس داده شده به بعد قرار می‌دهیم. با این کار آرایه ما یک واحد از اندیس داده شده یک خانه، به سمت جلو حرکت می‌کند و الان خانه index و index+1 دارای یک مقدار هستند که در خط بعدی مقدار جدید را داخل آن قرار می‌دهیم و متغیر count را به روز می‌کنیم. باقی موارد را چون پردازش‌های جست و جو، پیدا کردن اندیس یک المان و گزینه‌های حذف، به خودتان واگذار می‌کنم.

لیست‌های پیوندی Linked List - پیاده سازی پویا
همانطور که دیدید لیست‌های ایستا دارای مشکل بزرگی هستند و آن هم این است که با انجام هر عملی بر روی آرایه‌ها مانند افزودن، درج در مکانی خاص و همچنین حذف (خانه ای در آرایه خالی خواهد شد و خانه‌های جلوترش باید یک گام به عقب برگردند) نیاز است که خانه‌های آرایه دوباره مرتب شوند که هر چقدر میزان داده‌ها بیشتر باشد این مشکل بزرگتر شده و ناکارآمدی برنامه را افزایش خواهد داد.
این مشکل با لیست‌های پیوندی حل می‌گردد. در این ساختار هر المان حاوی اطلاعاتی از المان بعدی است و در لیست‌های پیوندی دوطرفه حاوی المان قبلی است. شکل زیر نمایش یک لیست پیوندی در حافظه است:

برای پیاده سازی آن به دو کلاس نیاز داریم. کلاس ListNode برای نگهداری هر المان و اطلاعات المان بعدی به کار می‌رود که از این به بعد به آن Node یا گره می‌گوییم و دیگری کلاس <DynamicList<T برای نگهداری دنباله ای از گره‌ها و متدهای پردازشی آن.

public class DynamicList<T>
{
    private class ListNode
    {
        public T Element { get; set; }
        public ListNode NextNode { get; set; }
 
        public ListNode(T element)
        {
            this.Element = element;
            NextNode = null;
        }
 
        public ListNode(T element, ListNode prevNode)
        {
            this.Element = element;
            prevNode.NextNode = this;
        }
    }
 
    private ListNode head;
    private ListNode tail;
    private int count;
 
    // …
}

از آن جا که نیازی نیست کاربر با کلاس ListNode آشنایی داشته باشد و با آن سر و کله بزند، آن را داخل همان کلاس اصلی به صورت خصوصی استفاده می‌کنیم. این کلاس دو خاصیت دارد؛ یکی برای المان اصلی و دیگر گره بعدی. این کلاس دارای دو سازنده است که اولی تنها برای عنصر اول به کار می‌رود. چون اولین بار است که یک گره ایجاد می‌شود، پس باید خاصیت NextNode یعنی گره بعدی در آن Null باشد و سازنده‌ی دوم برای گره‌های شماره 2 به بعد به کار می‌رود که همراه المان داده شده، گره قبلی را هم ارسال می‌کنیم تا خاصیت NextNode آن را به گره جدیدی که می‌سازیم مرتبط سازد. سه خاصیت کلاس اصلی به نام‌های Count,Tail,Head به ترتیب برای اشاره به اولین گره، آخرین گره و تعداد گره‌ها، به کار می‌روند که در ادامه کد آن‌را در زیر می‌بینیم:

public DynamicList()
{
    this.head = null;
    this.tail = null;
    this.count = 0;
}

public void Add(T item)
{
    if (this.head == null)
    {
        this.head = new ListNode(item);
        this.tail = this.head;
    }
    else
    {
        ListNode newNode = new ListNode(item, this.tail);
        this.tail = newNode;
    }
    this.count++;
}

سازنده مقدار دهی پیش فرض را انجام می‌دهد. در متد Add المان جدیدی باید افزوده شود؛ پس چک می‌کند این المان ارسالی قرار است اولین گره باشد یا خیر؟ اگر head که به اولین گره اشاره دارد Null باشد، به این معنی است که این اولین گره است. پس اولین سازنده‌ی کلاس ListNode را صدا می‌زنیم و آن را در متغیر Head قرار می‌دهیم و چون فقط همین گره را داریم، پس آخرین گره هم شناخته می‌شود که در tail نیز قرار می‌گیرد. حال اگر فرض کنیم المان بعدی را به آن بدهیم، اینبار دیگر Head برابر Null نخواهد بود. پس دومین سازنده‌ی ListNode صدا زده می‌شود که به غیر از المان جدید، باید آخرین گره قبلی هم با آن ارسال شود و گره جدیدی که ایجاد می‌شود در خاصیت NextNode آن نیز قرار بگیرد و در نهایت گره ایجاد شده به عنوان آخرین گره لیست در متغیر Tail نیز قرار می‌گیرد. در خط پایانی هم به هر مدلی که المان جدید به لیست اضافه شده باشد متغیر Count به روز می‌شود.

public T RemoveAt(int index)
{
    if (index >= count || index < 0)
    {
        throw new ArgumentOutOfRangeException(
            "Invalid index: " + index);
    }
 
    int currentIndex = 0;
    ListNode currentNode = this.head;
    ListNode prevNode = null;
    while (currentIndex < index)
    {
        prevNode = currentNode;
        currentNode = currentNode.NextNode;
        currentIndex++;
    }
 

    RemoveListNode(currentNode, prevNode);
 
    return currentNode.Element;
}

private void RemoveListNode(ListNode node, ListNode prevNode)
{
    count--;
    if (count == 0)
    {
        this.head = null;
        this.tail = null;
    }
    else if (prevNode == null)
    {
        this.head = node.NextNode;
    }
    else
    {
        prevNode.NextNode = node.NextNode;
    }

    if (object.ReferenceEquals(this.tail, node))
    {
        this.tail = prevNode;
    }
}

برای حذف یک گره شماره اندیس آن گره را دریافت می‌کنیم و از Head، گره را بیرون کشیده و با خاصیت nextNode آنقدر به سمت جلو حرکت می‌کنیم تا متغیر currentIndex یا اندیس داده شده برابر شود و سپس گره دریافتی و گره قبلی آن را به سمت تابع RemoveListNode ارسال می‌کنیم. کاری که این تابع انجام می‌دهد این است که مقدار NextNode گره فعلی که قصد حذفش را داریم به خاصیت Next Node گره قبلی انتساب می‌دهد. پس به این ترتیب پیوند این گره از لیست از دست می‌رود و گره قبلی به جای اشاره به این گره، به گره بعد از آن اشاره می‌کند. مابقی کد از قبیل جست و برگردان اندیس یک عنصر و ... را به خودتان وگذار می‌کنم.

در روش‌های بالا ما خودمان 2 عدد ADT را پیاده سازی کردیم و متوجه شدیم برای دخیره داده‌ها در حافظه روش‌های متفاوتی وجود دارند که بیشتر تفاوت آن در مورد استفاده از حافظه و کارآیی این روش هاست.


لیست‌های پیوندی دو طرفه Doubly Linked_List

لیست‌های پیوندی بالا یک طرفه بودند و اگر ما یک گره را داشتیم و می‌خواستیم به گره قبلی آن رجوع کنیم، اینکار ممکن نبود و مجبور بودیم برای رسیدن به آن از ابتدای گره حرکت را آغاز کنیم تا به آن برسیم. به همین منظور مبحث لیست‌های پیوندی دو طرفه آغاز شد. به این ترتیب هر گره به جز حفظ ارتباط با گره بعدی از طریق خاصیت NextNode، ارتباطش را با گره قبلی از طریق خاصیت PrevNode نیز حفظ می‌کند.

این مبحث را در اینجا می‌بندیم و در قسمت بعدی آن را ادامه می‌دهیم.

‫۹ سال و ۸ ماه قبل، پنجشنبه ۳۰ بهمن ۱۳۹۳، ساعت ۰۴:۵۰
وحید نصیری وحید نصیری
مطالب
طراحی گردش کاری با استفاده از State machines - قسمت سوم
در این قسمت، یک سری مثال گردش کاری سازگار با Stateless Designer را بررسی خواهیم کرد. خروجی‌های XML زیر را می‌توانید در Stateless Designer وارد کرده و تبدیل به کدهای معادل کنید. اگر نمونه‌ای را هم خودتان طراحی کرده‌اید می‌توانید در قسمت نظرات مطلب جاری به اشتراک بگذارید.


الف) طراحی گردش کاری یک سیستم ردیابی خطاها (Bug tracking system)

در ادامه رویدادها، حالات و انتقالات یک ماشین حالت ردیابی خطاها را مشاهده می‌کنید:

<statemachine xmlns="http://statelessdesigner.codeplex.com/Schema">
  <settings>
    <itemname>BugTrackingStateMachine</itemname>
    <namespace>StatelessTests</namespace>
    <class>public</class>
  </settings>
  <triggers>     
    <trigger>Assign</trigger>
    <trigger>Defer</trigger>
    <trigger>Resolve</trigger>
    <trigger>Close</trigger>
  </triggers>
  <states>     
    <state start="yes">Open</state>
    <state>Assigned</state>
    <state>Deferred</state>
    <state>Resolved</state>
    <state>Closed</state>
  </states>
  <transitions>
    <transition trigger="Assign" from="Open" to="Assigned" />
    <transition trigger="Assign" from="Assigned" to="Assigned" />
    <transition trigger="Close" from="Assigned" to="Closed" />
    <transition trigger="Defer" from="Assigned" to="Deferred" />
    <transition trigger="Assign" from="Deferred" to="Assigned" />
    <transition trigger="Resolve" from="Assigned" to="Resolved" />
  </transitions>
</statemachine>
با گرافی معادل:


توضیحات:
یک گزارش خطا حداقل پنج حالت آغاز (Open)، انتساب به شخص، جهت رفع مشکل (Assign)، به تاخیر افتادن/درحال بررسی (Deffered)، برطرف شده (Resolved) و خاتمه یافته/برطرف نخواهد شد (Closed) را می‌تواند داشته باشد.
برای حرکت (Transition) از هر حالت به حالتی دیگر نیاز به یک سری رویداد (Trigger) است که لیست آن‌ها را در بالا مشاهده می‌کنید.
در ابتدا سیستم در حالت انتساب به شخص قرار می‌گیرد. سپس در همین حالت شخص می‌تواند یکی از سه حالت رفع شده، بستن موضوع و یا ارجاع به زمانی دیگر را انتخاب کند. حتی در حالت ارجاع به شخص، شخص می‌تواند مساله را به شخصی دیگر ارجاع دهد. یا در حالت به تاخیر افتادن حل مساله، می‌توان مشکل را به شخصی دیگر انتساب داد.


ب) طراحی گردش کاری درخواست ارتقاء در یک شرکت

مراحل درخواست ارتقاء شغلی را در یک سازمان فرضی، در ذیل مشاهده می‌کنید:
<statemachine xmlns="http://statelessdesigner.codeplex.com/Schema">
  <settings>
    <itemname>RequestPromotionStateMachine</itemname>
    <namespace>StatelessTests</namespace>
    <class>public</class>
  </settings>
  <triggers>     
    <trigger>Complete</trigger>
    <trigger>RequestInfo</trigger>
    <trigger>Deny</trigger>
    <trigger>Approve</trigger>
    <trigger>ManagerJustify</trigger>
  </triggers>
  <states>     
    <state start="yes">RequestPromotionForm</state>
    <state>ManagerReview</state>
    <state>PromotionDenied</state>
    <state>VicePresidentApprove</state>
    <state>Promoted</state>
  </states>
  <transitions>
    <transition trigger="Complete" from="RequestPromotionForm" to="ManagerReview" />

    <transition trigger="RequestInfo" from="ManagerReview" to="RequestPromotionForm" />
    <transition trigger="Deny" from="ManagerReview" to="PromotionDenied" />
    <transition trigger="Approve" from="ManagerReview" to="VicePresidentApprove" />

    <transition trigger="ManagerJustify" from="VicePresidentApprove" to="ManagerReview" />
    <transition trigger="Deny" from="VicePresidentApprove" to="PromotionDenied" />
    <transition trigger="Approve" from="VicePresidentApprove" to="Promoted" />
  </transitions>
</statemachine>
با گرافی معادل:


توضیحات:
کارمند فرم درخواست ارتقاء را تکمیل می‌کند. این فرم به مسئول او ارسال می‌شود. مسئول می‌تواند درخواست را یک ضرب رد کند؛ یا تائید کند که سپس برای مدیرعامل شرکت ارسال می‌شود و یا مجددا به شخص برای تکمیل نواقص فرم ارجاع دهد. مدیرعامل شرکت می‌تواند درخواست را تائید کند که در اینجا کار خاتمه می‌یابد و شخص ارتقاء خواهد یافت. یا می‌تواند درخواست را رد کند و یا برای بررسی بیشتر مجددا به مسئول شخص ارجاع دهد.


تمرین! توضیحات زیر را تبدیل به یک State machine کنید!

چند سال قبل به اداره‌ی بیمه تامین اجتماعی منطقه مراجعه کردم. جهت دریافت ریز سوابق و انتقال آن‌ها به این مرکز ابتدا یک برگه دریافت شد. پر شد، بعد به صورت دستی (توسط بنده) به یک نفر دیگر ارجاع شد تا امضاء کند. سپس به صورت دستی به مسئول قسمت ارجاع شد تا امضاء کند. مجددا به صورت دستی به مدیر کل مجموعه ارجاع شد تا امضاء کند. سپس به صورت دستی به دبیرخانه برای پیگیری ارجاع شد. قرار است ظرف یک ماه تا 45 روز این سوابق از یک واحد دیگر به این واحد منتقل شوند!
بعد از 45 روز:
مراجعه به دبیرخانه: دریافت شماره پرونده رسیده.
گفته شد که به قسمت دریافت شماره مراجعه کنید. مراجعه شد، گفتند برو پرونده‌ات را بگیر بیار. رفتم زیر زمین، گفت که ما اینطوری پرونده نمی‌دیم! برو فرمش رو هم پر کن بیار. مراجعه شد به کارمند مربوطه، ایشان پس از مشورت با سایر همکاران به این نتیجه رسیدند که در این مرحله نیازی به مراجعه به زیر زمین نبوده! و باید به قسمت ثبت نام مجدد مراجعه کنید! چشم!  
اینجا هم مجددا فرم پر شد،‌ارجاع داده شده به معاون قسمت، امضاء کرد گفت برو دبیرخانه شماره بگیر. شماره گرفته شده بعد مجددا به همان قسمت ثبت نام مراجعه کردم، گفتند برو پرونده‌ات را از زیر زمین بگیر بیار! بعد از آوردن پرونده، ارجاع شد به صورت دستی به یک قسمت دیگر که سوابق وارد سیستم شود (هنوز نشده بود!). بعد از ثبت (نیم ساعت یا بیشتر ...)، مجددا به همان قسمت ثبت نام مراجعه کردم، گفت حالا برو یک شماره بگیر بیار. شماره گرفته شد از قسمتی دیگر و مراجعه مجدد به قسمت ثبت نام، یک نامه دیگر تهیه کرد، به سه نفر دیگر + دبیرخانه برای امضاء و شماره گرفتن ارجاع داده شد. اینجا تمام شد. بعد این موارد ارجاع شد به قسمت دیگری از شهر برای دریافت قبض پرداخت بیمه.
مطلب مرتبط
‫۱۱ سال و ۱۰ ماه قبل، سه‌شنبه ۱۲ دی ۱۳۹۱، ساعت ۱۸:۳۵