از آشوب تا نظم: دستیابی به درک الگوریتم ها از طریق تجسم

TL; DR

به‌عنوان توسعه‌دهنده‌ای که برای مصاحبه با شرکت‌های FAANG آماده می‌شود، متوجه شدم که با الگوریتم‌های ساده‌ای مانند پیمایش رشته و چک‌های پالیندروم دست و پنجه نرم می‌کنم. با این حال، من استقامت کردم و پس از 9 ماه کار سخت، توانستم بر الگوریتم های خاص تری مانند KMP تسلط پیدا کنم. در طول این مدت، برای تجسم نحوه عملکرد الگوریتم های مرتب سازی و نحوه مقایسه اعداد به یک دفترچه و خودکار تکیه کردم.

از کجا شروع شد

وقتی شروع به آماده شدن برای مصاحبه با شرکت‌های FAANG کردم، با الگوریتم‌های ساده‌ای مانند پیمایش رشته و چک‌های پالیندروم مشکل داشتم. زمان هایی بود که تقریباً تسلیم شدم، اما همیشه یکی از کسانی بودم که شروع کردم. همین رویکرد در اینجا اعمال شد و پس از نه ماه کار سخت، از تلاش با الگوریتم‌های ساده به درک الگوریتم‌های خاص‌تری مانند KMP (که خیلی دوستش دارم) رفتم.

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

ما همه توسعه دهنده هستیم

پس چرا پروژه ای ایجاد نکنیم که الگوریتم های مرتب سازی را به روشی کاربرپسندتر تجسم کند؟ علاوه بر این، نوشتن راه‌حل‌های الگوریتمی به زبانی دیگر فرصتی اضافی برای درک و یادگیری بهتر آنها فراهم می‌کند.

من از این فرصت استفاده کردم تا دانش خود را بهبود بخشم و درک قوی تری از مسیر مرتب سازی ایجاد کنم. با ایجاد یک برنامه تلفن همراه با استفاده از Flutter، من توانستم از تجربه خود در توسعه چند پلتفرمی برای ایجاد ابزاری موثر برای تجسم الگوریتم های پیچیده، به ویژه مرتب سازی، استفاده کنم. این به من امکان داد تا دانش و درک خود را از این الگوریتم‌ها بیشتر بهبود بخشم و در عین حال یک پلتفرم کاربر پسند برای دیگران ایجاد کنم تا همین کار را انجام دهند.

فلاتر یک ابزار مفید است

با تجربه خوب در توسعه برنامه های کاربردی چند پلتفرمی با استفاده از چارچوب Flutter، من تصمیم گرفتم از آن برای ایجاد یک برنامه تلفن همراه برای هر دو سیستم عامل اندروید و iOS استفاده کنم. در حال حاضر، اگر پشتیبانی اضافه کنم، همان کد می تواند روی پلتفرم های وب و دسکتاپ اجرا شود.

در طول فرآیند به دست آوردم:

• من توانستم همان الگوریتم‌هایی را که قبلاً روی Leetcode و AlgoExpert (هر دو منبع عالی برای آماده‌سازی مصاحبه) انجام داده بودم، با Dart روی پیاده‌سازی‌های جاوا بنویسم.
• من در مورد الگوی مدیریت ایالت ارائه دهنده (توصیه به استفاده از Riverpod) که قبلاً در پشته توسعه من نبود، یاد گرفتم. ارائه‌دهنده اجازه می‌دهد تا منطق و رابط کاربری را از هم جدا کند و به‌طور واکنشی رابط کاربری را با داده‌های مصرف‌شده به‌روزرسانی می‌کند و روند به‌روزرسانی‌ها را بسیار روان می‌کند.
• من همچنین تخیل خود را فراتر از حد معمول سوق دادم و مجموعه ای ساده از اعداد را به ویجت های بصری دلپذیر تبدیل کردم. برای ساده‌تر کردن درک الگوریتم‌ها، کاربران می‌توانند اعداد را روشن و خاموش کنند.

اجرای من

هر الگوریتم مرتب سازی از نسل BaseSort است که به نوبه خود یک ChangeNotifier است. جزئیات اجرای هر الگوریتم تحت اجرای خاص آن پوشش داده شده است: BubbleSort، HeapSort، InsertionSort، MergeSort و SelectionSort. BaseSort فقط بخش های اساسی هر الگوریتم، مانند مراجع اشاره گرهای چپ و راست، و همچنین نمایه قسمت مرتب شده را پوشش می دهد. این کلاس مسئول تولید داده های تصادفی و اطلاع رسانی به هر مشترک از یک مجموعه داده جدید است.

class BaseSort with ChangeNotifier {
  BaseSort() {
    generateData();
  }

  List<int> array = List.empty(growable: true);

  int left = -1;
  int right = -1;
  int sorted = -1;

  bool isSorting = false;

  @mustCallSuper
  void generateData() {
    array.clear();
    isSorting = false;
    int counter = 0;
    final rand = Random();
    left = -1;
    right = -1;
    sorted = -1;

    while (counter < 50) {
      // to show anything in case of 0 -> shifting it to 1
      array.add(rand.nextInt(99) + 1);
      counter++;
      notifyListeners();
    }
  }

  Future startSorting() async {}

  Future sleep() async {
    await Future.delayed(const Duration(milliseconds: 150), () {});
  }
}

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

abstract class BaseSortWidget extends StatelessWidget {
  @override
  Widget build(BuildContext context) => Card(
        margin: const EdgeInsets.all(8.0),
        elevation: 2.0,
        shape: const RoundedRectangleBorder(
          borderRadius: BorderRadius.all(Radius.circular(12.0)),
        ),
        child: Padding(
          padding: const EdgeInsets.all(12.0),
          child: Column(
            mainAxisAlignment: MainAxisAlignment.center,
            children: <Widget>[
              Text(
                algorithmName(),
                style: const TextStyle(fontWeight: FontWeight.bold),
                textAlign: TextAlign.center,
              ),
              const SizedBox(height: 10),
              consumerWidget(),
              const SizedBox(height: 10),
              Text(
                algorithmComplexity(),
                style: const TextStyle(fontWeight: FontWeight.bold),
                textAlign: TextAlign.center,
              ),
            ],
          ),
        ),
      );
}

هر پیاده سازی ویجت الگوریتم، به استثنای SelectionSort، به حالت زیر ساده شده است:

class HeapSortWidget extends BaseSortWidget {
  @override
  String algorithmName() => HEAP_SORT;

  @override
  String algorithmComplexity() => 'Time: O(n*log(n))  Space: O(1)';

  @override
  Widget consumerWidget() => Consumer<HeapSort>(
        builder: (context, state, _) => Row(
          mainAxisAlignment: MainAxisAlignment.center,
          crossAxisAlignment: CrossAxisAlignment.end,
          children: buildItemsArray(
            state.array,
            state.left,
            state.right,
            state.sorted,
            Colors.cyan,
          ),
        ),
      );
}

تمام قسمت‌های دیگر صرفاً برای اهداف زیبایی‌شناختی، ایجاد کدی تمیزتر و ظریف‌تر هستند. صفحه اصلی فهرستی از ویجت‌های مرتب‌سازی است.

Consumer<SortHolder>(
  builder: (context, types, _) {
    final List<Widget> widgets = types.generateWidgets(context);
    return widgets.isEmpty
        ? Center(
            child: Text(
              '$DRAWER_TITLE\n\n$EMPTY_MESSAGE',
              textAlign: TextAlign.center,
              style: Theme.of(context)
                  .textTheme
                  .bodyLarge
                  .copyWith(fontSize: 18.0),
            ),
          )
        : ListView(
            padding: const EdgeInsets.all(8),
            children: widgets,
          );
  },
)

هر زمان که ویجت ها را اضافه یا حذف می کنیم، صفحه با موارد بیشتر یا کمتر به روز می شود. برای نگهداری داده‌های مربوط به ویجت‌ها و به هم زدن داده‌ها/شروع مرتب‌سازی، از SortHolder استفاده کردیم.

منظره

نمای حاصل از کار من بسیار تمیز به نظر می رسد و به راحتی قابل درک است.

فرآیند مرتب سازی

مشاهده فرآیند مرتب سازی لذت واقعی است. به‌علاوه، با دیدن اینکه کدام داده‌ها مقایسه می‌شوند، راه آسان‌تری برای درک الگوریتم مرتب‌سازی است. اشاره گر سمت چپ با رنگ زرد و اشاره گر سمت راست با قرمز نمایش داده می شود. لذت ببرید!

خلاصه

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

من از همه کسانی که می خواهند در این پروژه شرکت کنند، می خواهم که از طریق درخواست های کششی در gitHub من مشارکت کنند. من خوشحالم که زمانی را برای دیدارهای کوتاه و همکاری اختصاص می دهم.