1
00:00:00,000 --> 00:00:00,500

2
00:00:00,500 --> 00:00:03,340
[เล่นเพลง]

3
00:00:03,340 --> 00:00:11,020

4
00:00:11,020 --> 00:00:14,010
>> DAVID ลัน: นี่คือ CS50

5
00:00:14,010 --> 00:00:18,090
และนี่คือทั้งสองเริ่มต้นและ
end-- เช่น literally-- เกือบสิ้นสุด

6
00:00:18,090 --> 00:00:18,825
หกสัปดาห์

7
00:00:18,825 --> 00:00:20,030

8
00:00:20,030 --> 00:00:22,640
>> ฉันคิดว่าฉันต้องการแบ่งปัน
นิด ๆ หน่อย ๆ ของความเป็นจริงที่สนุก

9
00:00:22,640 --> 00:00:25,370
ผมเคยดึงนี้เพิ่มขึ้นจาก
ข้อมูลภาคการศึกษาที่ผ่านมาของการตั้งค่า

10
00:00:25,370 --> 00:00:29,710
คุณอาจจะจำได้ว่าเราขอให้คุณในทุก
รูปแบบการตั้งค่า P ​​ถ้าคุณได้ดูออนไลน์

11
00:00:29,710 --> 00:00:31,580
หรือถ้าคุณได้เข้าร่วมในคน

12
00:00:31,580 --> 00:00:33,020
และนี่คือข้อมูล

13
00:00:33,020 --> 00:00:34,710
ดังนั้นวันนี้เป็นอย่างมากคาดเดาได้

14
00:00:34,710 --> 00:00:37,126
แต่เราอยากจะใช้บิต
เวลาอยู่กับคุณอย่างไรก็ตาม

15
00:00:37,126 --> 00:00:40,599
ทุกคนต้องการที่จะคาดเดาว่าทำไมนี้
กราฟเป็นหยักให้ขึ้นลงขึ้นลง

16
00:00:40,599 --> 00:00:41,265
เพื่อให้อย่างต่อเนื่อง?

17
00:00:41,265 --> 00:00:42,980

18
00:00:42,980 --> 00:00:45,130
สิ่งที่ทำในแต่ละของยอดเขา
และต่ำสุดเป็นตัวแทน?

19
00:00:45,130 --> 00:00:46,005
>> ผู้ชม: [ไม่ได้ยิน]

20
00:00:46,005 --> 00:00:47,002

21
00:00:47,002 --> 00:00:47,835
DAVID ลัน: แท้จริง

22
00:00:47,835 --> 00:00:50,900

23
00:00:50,900 --> 00:00:55,480
และอื่น ๆ ขันพระเจ้าห้าม
เราถือเป็นหนึ่งบรรยายในวันศุกร์ที่

24
00:00:55,480 --> 00:00:58,960
ที่จุดเริ่มต้นของภาคการศึกษาที่
นั่นคือสิ่งที่เราเห็นเกิดขึ้น

25
00:00:58,960 --> 00:01:03,430
ดังนั้นวันนี้เรามีส่วนร่วมในบิต
เพิ่มเติมเกี่ยวกับโครงสร้างข้อมูล

26
00:01:03,430 --> 00:01:06,660
และให้คุณมากกว่าของแข็ง
รูปแบบจิตสำหรับปัญหาที่ห้า

27
00:01:06,660 --> 00:01:07,450
ซึ่งเป็นตอนนี้ออก

28
00:01:07,450 --> 00:01:10,817
สะกดผิดนั้นเราจะ
มือคุณแฟ้มข้อความบาง 100,000

29
00:01:10,817 --> 00:01:12,650
บวกคำในภาษาอังกฤษและ
คุณกำลังจะมี

30
00:01:12,650 --> 00:01:17,770
ที่จะคิดออกว่าจะโหลดได้อย่างชาญฉลาด
ในหน่วยความจำลงใน RAM โดยใช้ข้อมูลบางส่วน

31
00:01:17,770 --> 00:01:19,330
โครงสร้างของตัวเลือกของคุณ

32
00:01:19,330 --> 00:01:22,470
>> ตอนนี้หนึ่งในโครงสร้างของข้อมูลดังกล่าวได้
เป็น แต่อาจจะไม่ควรจะเป็น

33
00:01:22,470 --> 00:01:25,630
รายการที่เชื่อมโยงง่ายอย่างเป็นธรรม
ที่เรานำมาใช้เป็นครั้งสุดท้าย

34
00:01:25,630 --> 00:01:29,220
และรายการที่เชื่อมโยงได้อย่างน้อย
หนึ่งในข้อได้เปรียบกว่าอาร์เรย์

35
00:01:29,220 --> 00:01:32,096
เป็นสิ่งหนึ่งประโยชน์จาก
รายการที่เชื่อมโยงเนื้อหา?

36
00:01:32,096 --> 00:01:32,950
>> ผู้ชม: แทรก

37
00:01:32,950 --> 00:01:33,908
>> DAVID ลัน: แทรก

38
00:01:33,908 --> 00:01:34,155

39
00:01:34,155 --> 00:01:35,196
คุณหมายถึงอะไรโดยที่?

40
00:01:35,196 --> 00:01:37,872
>> ผู้ชม: ทุกที่พร้อม
รายการ [ไม่ได้ยิน]

41
00:01:37,872 --> 00:01:38,770
>> DAVID ลัน: ดี

42
00:01:38,770 --> 00:01:42,090
เพื่อให้คุณสามารถแทรกองค์ประกอบใดก็ตาม
คุณต้องการอยู่ตรงกลางของรายการ

43
00:01:42,090 --> 00:01:45,490
โดยไม่ต้องสับอะไร
ซึ่งเราได้ข้อสรุปในการเรียงลำดับของเรา

44
00:01:45,490 --> 00:01:47,630
การอภิปรายไม่ได้
จำเป็นต้องเป็นสิ่งที่ดี

45
00:01:47,630 --> 00:01:51,200
เพราะมันต้องใช้เวลาที่จะย้ายจริง
ทั้งหมดของมนุษย์ที่ทางซ้ายหรือขวา

46
00:01:51,200 --> 00:01:55,540
และอื่น ๆ ที่มีรายชื่อที่เชื่อมโยงคุณสามารถ
เพียงจัดสรรด้วย malloc, โหนดใหม่

47
00:01:55,540 --> 00:01:58,385
แล้ว update คู่ของ
pointers-- สองสามการดำเนินงาน max--

48
00:01:58,385 --> 00:02:01,480
และเราสามารถที่จะเสียบใครบางคน
ในที่ใดก็ได้ในรายการ

49
00:02:01,480 --> 00:02:03,550
>> อะไรที่เป็นประโยชน์
เกี่ยวกับรายการที่เชื่อมโยงหรือไม่?

50
00:02:03,550 --> 00:02:04,980

51
00:02:04,980 --> 00:02:05,659
ใช่?

52
00:02:05,659 --> 00:02:06,534
>> ผู้ชม: [ไม่ได้ยิน]

53
00:02:06,534 --> 00:02:07,538

54
00:02:07,538 --> 00:02:08,413
DAVID ลันเพอร์เฟ

55
00:02:08,413 --> 00:02:10,590

56
00:02:10,590 --> 00:02:11,090
สมบูรณ์

57
00:02:11,090 --> 00:02:12,070
มันเป็นแบบไดนามิกจริงๆ

58
00:02:12,070 --> 00:02:15,100
และการที่คุณไม่ได้กระทำ,
ล่วงหน้าให้มีขนาดคงที่บางส่วน

59
00:02:15,100 --> 00:02:18,750
ก้อนของหน่วยความจำเช่นเดียวกับที่คุณจะต้อง
ที่จะมีอาร์เรย์คว่ำที่

60
00:02:18,750 --> 00:02:22,455
คือการที่คุณสามารถจัดสรรโหนดเฉพาะ
จึงมีความต้องการใช้เฉพาะพื้นที่มากที่สุดเท่าที่

61
00:02:22,455 --> 00:02:23,330
ตามที่คุณต้องการจริง

62
00:02:23,330 --> 00:02:26,830
ตรงกันข้ามกับอาร์เรย์คุณอาจ
ตั้งใจจัดสรรน้อยเกินไป

63
00:02:26,830 --> 00:02:28,871
และแล้วก็แค่ไป
จะมีอาการปวดคอ

64
00:02:28,871 --> 00:02:32,440
จัดสรรอาร์เรย์ใหญ่ใหม่คัดลอก
ทุกอย่างผ่านไปฟรีอาร์เรย์เก่า

65
00:02:32,440 --> 00:02:33,990
และจากนั้นย้ายเกี่ยวกับธุรกิจของคุณ

66
00:02:33,990 --> 00:02:37,479
หรือแย่ลงคุณอาจจัดสรรวิธี
หน่วยความจำมากกว่าที่คุณต้องการจริง

67
00:02:37,479 --> 00:02:40,520
และเพื่อให้คุณกำลังจะมีมาก
อาร์เรย์เบาบางประชากรจึงจะพูด

68
00:02:40,520 --> 00:02:44,350
>> ดังนั้นรายการที่เชื่อมโยงเหล่านี้จะช่วยให้คุณ
ข้อดีของพลวัตและความยืดหยุ่น

69
00:02:44,350 --> 00:02:46,080
ด้วยการแทรกและการลบ

70
00:02:46,080 --> 00:02:48,000
แต่แน่นอนจะต้องมีราคาที่จ่าย

71
00:02:48,000 --> 00:02:50,000
ในความเป็นจริงหนึ่งในรูปแบบ
สำรวจแบบทดสอบศูนย์

72
00:02:50,000 --> 00:02:52,430
เป็นคู่ค้าไม่ชอบ
เราได้เห็นป่านนี้

73
00:02:52,430 --> 00:02:56,161
ดังนั้นสิ่งที่เป็นราคาที่จ่ายหรือ
ข้อเสียของการเชื่อมโยงรายชื่อ?

74
00:02:56,161 --> 00:02:56,660
ใช่

75
00:02:56,660 --> 00:02:57,560
>> ผู้ชม: ไม่มีการเข้าถึงแบบสุ่ม

76
00:02:57,560 --> 00:02:58,809
>> DAVID ลัน: ไม่เข้าถึงโดยสุ่ม

77
00:02:58,809 --> 00:02:59,540
แต่ผู้ที่ใส่ใจ?

78
00:02:59,540 --> 00:03:01,546
เข้าถึงโดยสุ่มไม่ได้เสียงที่น่าสนใจ

79
00:03:01,546 --> 00:03:02,421
>> ผู้ชม: [ไม่ได้ยิน]

80
00:03:02,421 --> 00:03:04,865

81
00:03:04,865 --> 00:03:05,740
DAVID ลัน: แน่นอน

82
00:03:05,740 --> 00:03:07,580
ถ้าคุณต้องการที่จะมี
algorithm-- บางอย่าง

83
00:03:07,580 --> 00:03:10,170
และแจ้งให้เราจริงเสนอ
ค้นหาแบบไบนารีโดยเฉพาะอย่างยิ่งที่

84
00:03:10,170 --> 00:03:12,600
เป็นหนึ่งที่เราได้ใช้ค่อนข้าง bit--
ถ้าคุณไม่ได้มีการเข้าถึงแบบสุ่ม

85
00:03:12,600 --> 00:03:15,516
คุณไม่สามารถทำอย่างนั้นคณิตศาสตร์ที่เรียบง่าย
ในการค้นหาเช่นองค์ประกอบกลาง

86
00:03:15,516 --> 00:03:16,530
และกระโดดขวาไป

87
00:03:16,530 --> 00:03:20,239
คุณแทนจะต้องเริ่มต้นในตอนแรก
องค์ประกอบและเป็นเส้นตรงค้นหาจากซ้าย

88
00:03:20,239 --> 00:03:22,780
ไปทางขวาถ้าคุณต้องการที่จะหา
กลางหรือองค์ประกอบอื่น ๆ

89
00:03:22,780 --> 00:03:24,410
>> ผู้ชม: มันอาจใช้เวลาหน่วยความจำเพิ่มเติม

90
00:03:24,410 --> 00:03:25,040
>> DAVID ลัน: ใช้หน่วยความจำมากขึ้น

91
00:03:25,040 --> 00:03:27,464
อยู่ที่ไหนที่เพิ่มเติม
ค่าใช้จ่ายที่มาจากในหน่วยความจำ?

92
00:03:27,464 --> 00:03:28,339
>> ผู้ชม: [ไม่ได้ยิน]

93
00:03:28,339 --> 00:03:32,566

94
00:03:32,566 --> 00:03:33,440
DAVID ลัน: แน่นอน

95
00:03:33,440 --> 00:03:35,679
ในกรณีนี้ที่นี่เรามี
รายการที่เชื่อมโยงสำหรับจำนวนเต็ม

96
00:03:35,679 --> 00:03:37,470
และยังเรากำลังเสแสร้ง
จำนวนหน่วยความจำ

97
00:03:37,470 --> 00:03:39,680
ที่เราต้องการโดยยังเก็บคำแนะนำเหล่านี้

98
00:03:39,680 --> 00:03:42,090
ตอนนี้น้อยกว่าการจัดการที่ใหญ่เป็น
structs ของคุณได้รับขนาดใหญ่

99
00:03:42,090 --> 00:03:45,320
และคุณไม่ได้จัดเก็บตัวเลข แต่
บางทีนักเรียนหรือวัตถุอื่น ๆ

100
00:03:45,320 --> 00:03:46,880
แต่จุดแน่นอนยังคงอยู่

101
00:03:46,880 --> 00:03:49,421
และดังนั้นจำนวนของการดำเนินงาน
อยู่ในรายชื่อที่เชื่อมโยงถูกเรียกว่า

102
00:03:49,421 --> 00:03:50,570
มี O ใหญ่ของ n-- เชิงเส้น

103
00:03:50,570 --> 00:03:54,730
สิ่งที่ต้องการแทรกหรือการค้นหา
หรือลบในกรณีองค์ประกอบ

104
00:03:54,730 --> 00:03:57,720
จะเกิดขึ้นที่ปลายสุดของ
รายการไม่ว่าจะเป็นการจัดเรียงหรือไม่

105
00:03:57,720 --> 00:04:01,167
>> บางครั้งคุณอาจได้รับโชคดีและใน
ขอบเขตเพื่อให้ลดลงในการดำเนินงานเหล่านี้

106
00:04:01,167 --> 00:04:04,250
นอกจากนี้ยังอาจจะมีเวลาคงที่ถ้าคุณอยู่
มักจะมองที่องค์ประกอบแรก

107
00:04:04,250 --> 00:04:05,070
เช่น

108
00:04:05,070 --> 00:04:09,360
แต่ในท้ายที่สุดเราสัญญาว่า
เพื่อให้บรรลุจอกศักดิ์สิทธิ์

109
00:04:09,360 --> 00:04:12,630
โครงสร้างข้อมูลหรือ
บางส่วนดังกล่าวประมาณ

110
00:04:12,630 --> 00:04:14,290
โดยวิธีการของเวลาอย่างต่อเนื่อง

111
00:04:14,290 --> 00:04:17,579
เราสามารถหาองค์ประกอบหรือเพิ่มองค์ประกอบ
หรือเอาองค์ประกอบจากรายการ?

112
00:04:17,579 --> 00:04:19,059
เราจะได้เห็นค่อนข้างเร็ว ๆ นี้

113
00:04:19,059 --> 00:04:21,100
และปรากฎว่า
กลไกที่เรากำลัง

114
00:04:21,100 --> 00:04:23,464
จะเริ่มต้นที่จะใช้ในวันนี้
การใช้งานประจำปีใน P ตั้งห้า

115
00:04:23,464 --> 00:04:24,630
เป็นจริงที่คุ้นเคยสวย

116
00:04:24,630 --> 00:04:27,430
ยกตัวอย่างเช่นถ้าเป็นพวง
หนังสือสอบแต่ละที่

117
00:04:27,430 --> 00:04:29,660
มีนักเรียนเป็นครั้งแรก
ชื่อและนามสกุลที่มัน

118
00:04:29,660 --> 00:04:31,820
และผมเลือกพวกเขาขึ้นมาจาก
ในตอนท้ายของการสอบ,

119
00:04:31,820 --> 00:04:33,746
และพวกเขากำลังทั้งหมดสวย
มากในลำดับแบบสุ่ม

120
00:04:33,746 --> 00:04:36,370
และเราต้องการที่จะไปเกี่ยวกับการเรียงลำดับ
การสอบเหล่านี้เพื่อให้คะแนนอีกครั้ง

121
00:04:36,370 --> 00:04:38,661
มันเป็นเพียงมากขึ้นและ
ได้เร็วขึ้นจะส่งพวกเขากลับออกมา

122
00:04:38,661 --> 00:04:40,030
ให้กับนักเรียนตามลำดับตัวอักษร

123
00:04:40,030 --> 00:04:42,770
สิ่งที่สัญชาตญาณของคุณจะ
สำหรับกองการสอบเช่นนี้?

124
00:04:42,770 --> 00:04:45,019
>> ดีถ้าคุณต้องการฉันคุณ
อาจจะเห็นว่านี่เป็นเมตร

125
00:04:45,019 --> 00:04:48,505
ดังนั้นฉันจะเรียงลำดับของการวางนี้ใน,
ถ้าเป็นโต๊ะหรือพื้นของฉันที่ฉัน

126
00:04:48,505 --> 00:04:50,650
ฉันแพร่กระจายสิ่งที่
แทนดูหรืออาเรย์ของฉันนะ

127
00:04:50,650 --> 00:04:52,210
ฉันอาจจะใส่ทั้งหมดของ Ms ในนั้น

128
00:04:52,210 --> 00:04:52,710
โอ้

129
00:04:52,710 --> 00:04:55,020
นี่ A. ดังนั้นฉันอาจ
ใส่เป็นมากกว่าที่นี่

130
00:04:55,020 --> 00:04:55,520
โอ้

131
00:04:55,520 --> 00:04:57,980
A. ที่นี่ฉันจะอื่น
ที่จะนำว่ากว่าที่นี่

132
00:04:57,980 --> 00:05:02,490
นี่ Z. เป็นนี่คือเอ็มอีกและดังนั้น
ฉันอาจจะเริ่มต้นสร้างกองเช่นนี้

133
00:05:02,490 --> 00:05:06,620
แล้วบางทีผมอาจจะไปในภายหลัง
และการเรียงลำดับของ nitpicky-Ly มากการจัดเรียง

134
00:05:06,620 --> 00:05:07,710
แต่ละกอง

135
00:05:07,710 --> 00:05:11,300
แต่ประเด็นก็คือผมจะดู
ที่ใส่ว่าฉันมือ

136
00:05:11,300 --> 00:05:14,016
และฉันจะทำให้บางคำนวณ
การตัดสินใจบนพื้นฐานของข้อมูลที่

137
00:05:14,016 --> 00:05:15,640
ถ้ามันเริ่มต้นด้วยใส่ไว้ที่นั่น

138
00:05:15,640 --> 00:05:18,980
ถ้ามันเริ่มต้นด้วย Z ใส่มันไป
มีและทุกสิ่งในระหว่าง

139
00:05:18,980 --> 00:05:22,730
>> ดังนั้นนี่คือเทคนิคที่เป็น
ที่รู้จักกันทั่วไป hashing-- H-A-S-H--

140
00:05:22,730 --> 00:05:26,550
ซึ่งโดยทั่วไปหมายถึงการเป็น
การป้อนข้อมูลและการใช้ข้อมูลที่จะคำนวณ

141
00:05:26,550 --> 00:05:30,940
ค่าทั่วไปจำนวนและที่
ตัวเลขดัชนีลงในการจัดเก็บข้อมูล

142
00:05:30,940 --> 00:05:32,260
ภาชนะเช่นอาร์เรย์

143
00:05:32,260 --> 00:05:35,490
ดังนั้นในคำอื่น ๆ ที่ผมอาจจะมี
ฟังก์ชันแฮชที่ผมทำในหัวของฉัน

144
00:05:35,490 --> 00:05:37,940
ว่าถ้าผมเห็นใครบางคนเป็น
ชื่อที่เริ่มต้นด้วย,

145
00:05:37,940 --> 00:05:40,190
ฉันกำลังจะไปที่แผนที่
ให้เป็นศูนย์ในหัวของฉัน

146
00:05:40,190 --> 00:05:44,160
และถ้าฉันเห็นคนที่มี Z ฉัน
จะ map ที่ 25 ในหัวของฉัน

147
00:05:44,160 --> 00:05:46,220
แล้วใส่ลงใน
กองส่วนใหญ่ที่ผ่านมา

148
00:05:46,220 --> 00:05:50,990
>> ตอนนี้ถ้าคุณคิดเกี่ยวกับการไม่สมองของฉัน
แต่โปรแกรม C หมายเลขสิ่งที่สามารถทำได้

149
00:05:50,990 --> 00:05:53,170
คุณพึ่งพาเพื่อให้บรรลุผลที่เหมือนกันหรือไม่

150
00:05:53,170 --> 00:05:55,594
ในคำอื่น ๆ ถ้าคุณ
มีตัวอักษร ASCII,

151
00:05:55,594 --> 00:05:57,510
วิธีการทำคุณกำหนด
สิ่งที่ถังที่จะนำมันมีอะไรบ้าง?

152
00:05:57,510 --> 00:05:59,801
คุณอาจไม่ต้องการที่จะ
ใส่มันลงไปในถัง 65 ซึ่ง

153
00:05:59,801 --> 00:06:01,840
จะเป็นเช่นนั่น
ไม่มีเหตุผลที่ดี

154
00:06:01,840 --> 00:06:04,320
ที่คุณต้องการที่จะนำ
ในแง่ของค่า ASCII หรือไม่?

155
00:06:04,320 --> 00:06:05,600

156
00:06:05,600 --> 00:06:08,920
ที่คุณต้องการที่จะทำเพื่อ ASCII ของ
มูลค่าให้เกิดขึ้นกับถังอย่างชาญฉลาด

157
00:06:08,920 --> 00:06:09,480
ที่จะนำมันมีอะไรบ้าง?

158
00:06:09,480 --> 00:06:10,206
>> ผู้ชม: ลบ A.

159
00:06:10,206 --> 00:06:10,956
>> DAVID ลัน: ใช่

160
00:06:10,956 --> 00:06:13,190
เพื่อลบหรือลบ
เฉพาะ 65 ถ้ามัน

161
00:06:13,190 --> 00:06:18,240
A. ทุนหรือ 98 ถ้า
มันเป็นตัวพิมพ์เล็ก

162
00:06:18,240 --> 00:06:21,300
และเพื่อที่จะช่วยให้เราสามารถมาก
เพียงและมาก arithmetically,

163
00:06:21,300 --> 00:06:23,260
ใส่อะไรลงไปในถังเช่นนั้น

164
00:06:23,260 --> 00:06:26,010
ดังนั้นมันจะเปิดออกที่เราทำจริง
นี้ได้ดีกับแบบทดสอบ

165
00:06:26,010 --> 00:06:29,051
>> ดังนั้นคุณอาจจำคุณวงกลมของคุณ
ชื่อการเรียนการสอนของเพื่อนบนหน้าปก

166
00:06:29,051 --> 00:06:32,270
และชื่อของ TF ถูกจัด
ลงในคอลัมน์เหล่านี้ตามลำดับตัวอักษร

167
00:06:32,270 --> 00:06:34,400
ดีเชื่อหรือไม่ว่า
เมื่อทั้งหมด 80 บวกของเรา

168
00:06:34,400 --> 00:06:37,800
ได้ร่วมกันคืนอื่น ๆ ที่จะเกรด
ขั้นตอนสุดท้ายในกระบวนการการจัดลำดับของเรา

169
00:06:37,800 --> 00:06:41,830
คือการสับแบบทดสอบเป็นใหญ่
พื้นที่ของชั้นที่ [ไม่ได้ยิน]

170
00:06:41,830 --> 00:06:45,110
และการวางแบบทดสอบของทุกคนออกมา
ในตรงคำสั่งของ TF ของพวกเขา

171
00:06:45,110 --> 00:06:47,700
ชื่อบนหน้าปกเพราะ
แล้วมันง่ายมากสำหรับเรา

172
00:06:47,700 --> 00:06:51,290
การค้นหาผ่านว่าการใช้เส้นตรง
ค้นหาหรือชนิดของความฉลาดบาง

173
00:06:51,290 --> 00:06:54,050
สำหรับ TF ไปหาเขาหรือ
นักเรียนของเธอ 'แบบทดสอบ

174
00:06:54,050 --> 00:06:56,060
>> ดังนั้นความคิดของ hashing นี้
ที่คุณจะเห็นคือ

175
00:06:56,060 --> 00:07:00,520
มีประสิทธิภาพมากสวยจริง
เป็นเรื่องธรรมดาและใช้งานง่ายมาก

176
00:07:00,520 --> 00:07:03,000
เหมือนบางทีอาจจะแบ่งและ
ชนะในสัปดาห์ที่ศูนย์

177
00:07:03,000 --> 00:07:05,250
ฉันอย่างรวดเร็วไปข้างหน้าเพื่อ Hackathon
สองสามปีที่ผ่านมา

178
00:07:05,250 --> 00:07:08,040
นี่คือ Zamyla และคู่ของ
นักเรียนอวยพรเจ้าหน้าที่อื่น ๆ

179
00:07:08,040 --> 00:07:09,030
ขณะที่พวกเขาเดินเข้ามาใน

180
00:07:09,030 --> 00:07:12,680
และเรามีทั้งกลุ่มของการพับ
มีตารางที่มีแท็กชื่อ

181
00:07:12,680 --> 00:07:15,380
และเรามีแท็กชื่อที่จัด
ด้วยเช่นเป็นที่นั่น

182
00:07:15,380 --> 00:07:16,690
และ Zs ที่นั่น

183
00:07:16,690 --> 00:07:20,350
และเพื่อให้เป็นหนึ่งใน TFS อย่างชาญฉลาด
เขียนนี้เป็นคำแนะนำ

184
00:07:20,350 --> 00:07:21,030
สำหรับวันที่

185
00:07:21,030 --> 00:07:24,480
และในสัปดาห์ที่ 12 ของภาคการศึกษานี้
ทั้งหมดทำให้ความรู้สึกที่สมบูรณ์แบบและทุกคน

186
00:07:24,480 --> 00:07:25,310
รู้ว่าจะทำอย่างไร

187
00:07:25,310 --> 00:07:27,900
แต่เมื่อใดที่คุณได้
เข้าคิวในทางเดียวกัน

188
00:07:27,900 --> 00:07:30,272
คุณกำลังดำเนินการ
ความคิดเดียวกับกัญชา

189
00:07:30,272 --> 00:07:31,730
ดังนั้นขอให้เป็นระเบียบแบบแผนมันนิด ๆ หน่อย ๆ

190
00:07:31,730 --> 00:07:32,890
นี่คืออาร์เรย์

191
00:07:32,890 --> 00:07:36,820
มันดึงไปเป็นเพียงเล็กน้อย
กว้างเพียงเพื่อให้เห็นภาพ, สายตา

192
00:07:36,820 --> 00:07:38,920
ที่เราอาจจะวางสาย
ในบางสิ่งบางอย่างเช่นนี้

193
00:07:38,920 --> 00:07:41,970
และอาเรย์นี้
อย่างเห็นได้ชัดขนาดทั้งหมด 26

194
00:07:41,970 --> 00:07:43,935
และสิ่งที่เรียกว่า
ตารางพล

195
00:07:43,935 --> 00:07:48,930
แต่นี่เป็นเพียงการกระทำของศิลปิน
ของสิ่งที่ตารางแฮชอาจจะ

196
00:07:48,930 --> 00:07:52,799
>> ดังนั้นตารางแฮชตอนนี้เป็นไปได้
เป็นระดับโครงสร้างข้อมูลที่สูงขึ้น

197
00:07:52,799 --> 00:07:54,840
ในตอนท้ายของวัน
เรากำลังจะเห็นว่าคุณ

198
00:07:54,840 --> 00:07:58,700
สามารถใช้ตารางแฮชซึ่ง
เป็นเหมือนเส้นเช็คอิน

199
00:07:58,700 --> 00:08:02,059
ที่ Hackathon มากเช่นนี้
ตารางที่ใช้สำหรับการจัดเรียงหนังสือสอบ

200
00:08:02,059 --> 00:08:03,850
แต่ตารางแฮชเป็น
การเรียงลำดับของระดับสูงนี้

201
00:08:03,850 --> 00:08:08,250
แนวความคิดที่จะใช้อาร์เรย์
ใต้ฝากระโปรงจะใช้มัน

202
00:08:08,250 --> 00:08:11,890
หรืออาจใช้รายการความยาวหรือแม้กระทั่ง
บางทีบางโครงสร้างข้อมูลอื่น ๆ

203
00:08:11,890 --> 00:08:15,590
และตอนนี้ที่การ theme--
บางส่วนของส่วนผสมพื้นฐานเหล่านี้

204
00:08:15,590 --> 00:08:18,310
เช่นอาร์เรย์และอาคารหลังนี้
ปิดกั้นตอนนี้ของรายการความยาว

205
00:08:18,310 --> 00:08:21,740
และเห็นว่าอะไรที่เราสามารถสร้าง
ด้านบนของคนเช่นส่วนผสม

206
00:08:21,740 --> 00:08:26,550
เป็นสูตรที่ทำให้มากขึ้นและมากขึ้น
ผลสุดท้ายที่น่าสนใจและมีประโยชน์

207
00:08:26,550 --> 00:08:28,680
>> ดังนั้นด้วยตารางแฮช
เราอาจจะใช้มัน

208
00:08:28,680 --> 00:08:32,540
ในหน่วยความจำ pictorially เช่นนี้ แต่
ว่าอาจเป็นจริงจะเขียนขึ้นมา?

209
00:08:32,540 --> 00:08:33,789
ดีอาจจะเป็นเพียงนี้

210
00:08:33,789 --> 00:08:38,270
ถ้าความจุในตัวพิมพ์ใหญ่ทั้งหมดเป็นเพียง
constant-- บางอย่างเช่น 26,

211
00:08:38,270 --> 00:08:42,030
สำหรับ 26 ตัวอักษรของ alphabet--
ผมอาจจะเรียกตารางตัวแปรของฉัน

212
00:08:42,030 --> 00:08:45,630
และฉันอาจจะอ้างว่าฉันจะ
ใส่ดาวถ่านในนั้นหรือสตริง

213
00:08:45,630 --> 00:08:49,880
ดังนั้นจึงเป็นเรื่องง่ายอย่างที่นี้ถ้าคุณ
ต้องการที่จะใช้ตารางแฮช

214
00:08:49,880 --> 00:08:51,490
และยังนี้เป็นจริงเพียงอาร์เรย์

215
00:08:51,490 --> 00:08:53,198
แต่อีกครั้งกัญชา
ตารางอยู่ในขณะนี้สิ่งที่เราจะ

216
00:08:53,198 --> 00:08:57,470
เรียกชนิดข้อมูลนามธรรมที่เป็นเพียง
การเรียงลำดับของความคิดฝังรากลึกอยู่ด้านบน

217
00:08:57,470 --> 00:09:00,780
บางสิ่งบางอย่างทางโลกมากขึ้น
ตอนนี้ชอบอาร์เรย์

218
00:09:00,780 --> 00:09:02,960
>> ตอนนี้วิธีที่เราทำไป
เกี่ยวกับการแก้ปัญหา?

219
00:09:02,960 --> 00:09:06,980
ดีก่อนหน้านี้ผมก็มีความหรูหรา
ของการมีพื้นที่ตารางพอที่นี่

220
00:09:06,980 --> 00:09:09,460
เพื่อที่ฉันจะใส่
จิปาถะที่ใดก็ได้ที่ฉันต้องการ

221
00:09:09,460 --> 00:09:10,620
ดังนั้นในฐานะที่จะไปที่นี่

222
00:09:10,620 --> 00:09:12,100
Zs อาจจะไปที่นี่

223
00:09:12,100 --> 00:09:13,230
นางสาวอาจจะไปที่นี่

224
00:09:13,230 --> 00:09:14,740
แล้วผมก็มีบางพื้นที่พิเศษ

225
00:09:14,740 --> 00:09:18,740
แต่นี้เป็นบิตของโกงขวา
ในขณะนี้เพราะตารางนี้ถ้าผมจริงๆ

226
00:09:18,740 --> 00:09:22,720
คิดว่ามันเป็นอาเรย์เป็นเพียง
จะมีขนาดคงที่บางส่วน

227
00:09:22,720 --> 00:09:25,380
>> ดังนั้นในทางเทคนิคถ้าผมดึง
ขึ้นแบบทดสอบของนักเรียนอีก

228
00:09:25,380 --> 00:09:28,490
และดูโอ้คนนี้
ชื่อเริ่มต้นด้วยเกินไป

229
00:09:28,490 --> 00:09:30,980
ชนิดของฉันต้องการที่จะนำมันมี

230
00:09:30,980 --> 00:09:34,740
แต่ทันทีที่ฉันวางมันมีถ้า
ตารางนี้แน่นอนเป็นอาร์เรย์

231
00:09:34,740 --> 00:09:37,840
ฉันจะได้รับการเอาชนะหรือ clobbering
ใครก็ตามที่ทำแบบทดสอบของนักเรียนนี้

232
00:09:37,840 --> 00:09:38,340
ใช่มั้ย?

233
00:09:38,340 --> 00:09:41,972
หากเป็นอาร์เรย์เพียงสิ่งเดียวสามารถ
ไปในแต่ละเซลล์เหล่านี้หรือองค์ประกอบ

234
00:09:41,972 --> 00:09:43,680
และดังนั้นผมชนิดของมี
ที่จะเลือกและเลือก

235
00:09:43,680 --> 00:09:45,735
>> ก่อนหน้านี้ตอนนี้ผมชนิด
โกงและทำอย่างนี้หรือฉัน

236
00:09:45,735 --> 00:09:47,526
เพียงแค่ซ้อนชนิดของ
พวกเขาให้เหนือคนอื่น ๆ

237
00:09:47,526 --> 00:09:49,170
แต่ที่ไม่ได้ไปบินในรหัส

238
00:09:49,170 --> 00:09:52,260
เพื่อที่ฉันจะใส่
นักเรียนที่สองที่มีชื่อ

239
00:09:52,260 --> 00:09:54,964
คือถ้าสิ่งที่ผมต้องเป็นแบบนี้
พื้นที่ตารางใช้ได้?

240
00:09:54,964 --> 00:09:57,880
และฉันได้ใช้สามช่องและมัน
มีลักษณะอื่น ๆ เช่นมีเพียงไม่กี่

241
00:09:57,880 --> 00:09:58,959
สิ่งที่คุณสามารถทำอะไรได้บ้าง

242
00:09:58,959 --> 00:09:59,834
ผู้ชม: [ไม่ได้ยิน]

243
00:09:59,834 --> 00:10:00,565

244
00:10:00,565 --> 00:10:01,315
DAVID ลัน: ใช่

245
00:10:01,315 --> 00:10:02,370
บางทีขอเพียงแค่ให้มันง่าย

246
00:10:02,370 --> 00:10:02,660
ใช่มั้ย?

247
00:10:02,660 --> 00:10:04,243
มันไม่พอดีที่ฉันต้องการที่จะนำมัน

248
00:10:04,243 --> 00:10:07,450
ดังนั้นฉันจะใส่มัน
ในทางเทคนิคที่ B จะไป

249
00:10:07,450 --> 00:10:09,932
ตอนนี้แน่นอนผมเริ่มต้น
การวาดตัวเองในมุม

250
00:10:09,932 --> 00:10:11,890
ถ้าฉันได้รับนักเรียน
ที่มีชื่อเป็นจริง B,

251
00:10:11,890 --> 00:10:14,840
ตอนนี้ B จะถูกย้ายไปเล็ก ๆ น้อย ๆ
ไปข้างหน้าในขณะที่อาจจะเกิดขึ้นครับ

252
00:10:14,840 --> 00:10:17,530
ถ้าเป็น B ตอนนี้มันได้ไปที่นี่

253
00:10:17,530 --> 00:10:20,180
>> และเพื่อให้ได้อย่างรวดเร็ว
อาจจะกลายเป็นปัญหา

254
00:10:20,180 --> 00:10:23,850
แต่มันก็เป็นเทคนิคที่จริง
จะเรียกว่าเป็นเส้นละเอียด,

255
00:10:23,850 --> 00:10:26,650
โดยคุณเพียงแค่พิจารณาของคุณ
อาเรย์ที่จะเป็นไปตามเส้น

256
00:10:26,650 --> 00:10:29,680
และคุณเพียงแค่ชนิดของการสอบสวนหรือ
ตรวจสอบในแต่ละองค์ประกอบ

257
00:10:29,680 --> 00:10:31,360
มองหาจุดที่สามารถใช้ได้

258
00:10:31,360 --> 00:10:34,010
และทันทีที่คุณพบว่า
หนึ่งที่คุณวางไว้ในที่นั่น

259
00:10:34,010 --> 00:10:38,390
>> ตอนนี้ราคาการจ่ายเงินตอนนี้
สำหรับการแก้ปัญหานี้คืออะไร?

260
00:10:38,390 --> 00:10:41,300
เรามีอาร์เรย์ขนาดคงที่
และเมื่อฉันใส่ชื่อ

261
00:10:41,300 --> 00:10:44,059
ลงไปอย่างน้อยในขั้นต้นว่ามีอะไร
เวลาทำงานของการแทรก

262
00:10:44,059 --> 00:10:46,350
สำหรับการวางของนักเรียน
แบบทดสอบในถังที่เหมาะสมหรือไม่

263
00:10:46,350 --> 00:10:48,710

264
00:10:48,710 --> 00:10:50,002
Big O ของสิ่งที่?

265
00:10:50,002 --> 00:10:51,147
>> ผู้ชม: n

266
00:10:51,147 --> 00:10:52,480
DAVID ลัน: ฉันได้ยิน O ใหญ่ของ n

267
00:10:52,480 --> 00:10:53,530

268
00:10:53,530 --> 00:10:54,300
ไม่เป็นความจริง

269
00:10:54,300 --> 00:10:56,490
แต่เราจะหยอกล้อกัน
ทำไมในเวลาเพียงสักครู่

270
00:10:56,490 --> 00:10:57,702
อะไรมันอาจจะมี?

271
00:10:57,702 --> 00:10:58,755
>> ผู้ชม: [ไม่ได้ยิน]

272
00:10:58,755 --> 00:11:00,380
DAVID ลัน: และให้ฉันทำมันสายตา

273
00:11:00,380 --> 00:11:04,720
ดังนั้นคิดว่านี้เป็นตัวอักษรเอส

274
00:11:04,720 --> 00:11:05,604
>> ผู้ชม: มันเป็นหนึ่งใน

275
00:11:05,604 --> 00:11:06,520
DAVID ลัน: มันเป็นหนึ่งใน

276
00:11:06,520 --> 00:11:06,710
ใช่มั้ย?

277
00:11:06,710 --> 00:11:08,950
นี้เป็นอาเรย์ซึ่ง
หมายความว่าเรามีการเข้าถึงแบบสุ่ม

278
00:11:08,950 --> 00:11:11,790
และถ้าเราคิดว่าเรื่องนี้
เป็นศูนย์และนี่เป็น 25

279
00:11:11,790 --> 00:11:13,800
และเราตระหนักว่า
โอ้นี่เป็นสัญญาณ S ของฉัน

280
00:11:13,800 --> 00:11:16,350
แน่นอนฉันจะแปลง
S, อักขระ ASCII,

281
00:11:16,350 --> 00:11:18,540
ให้เป็นตัวเลขที่สอดคล้อง
ระหว่างศูนย์และ 25

282
00:11:18,540 --> 00:11:20,910
และแล้วทันที
วางไว้ที่มันอยู่

283
00:11:20,910 --> 00:11:26,120
>> แต่แน่นอนเร็วที่สุดเท่าที่ฉันได้รับการ
คนที่สองที่ชื่อเป็น A หรือ B หรือ C

284
00:11:26,120 --> 00:11:29,300
ในที่สุดถ้าผมเคยใช้
เส้นละเอียดเป็นวิธีแก้ปัญหาของฉัน

285
00:11:29,300 --> 00:11:31,360
เวลาทำงานของ
แทรกในกรณีที่เลวร้ายที่สุด

286
00:11:31,360 --> 00:11:33,120
เป็นจริงจะตกมาอยู่ในสิ่งที่?

287
00:11:33,120 --> 00:11:34,270

288
00:11:34,270 --> 00:11:36,045
และฉันไม่ได้ยินมันนี่
ได้อย่างถูกต้องในช่วงต้น

289
00:11:36,045 --> 00:11:36,920
ผู้ชม: [ไม่ได้ยิน]

290
00:11:36,920 --> 00:11:41,620
DAVID ลัน: ดังนั้นจึงเป็น n แน่นอนอีกครั้ง
คุณมีชุดข้อมูลที่มีขนาดใหญ่พอสมควร

291
00:11:41,620 --> 00:11:44,410
ดังนั้นในแง่หนึ่งหาก
อาเรย์ของคุณมีขนาดใหญ่พอ

292
00:11:44,410 --> 00:11:48,287
และข้อมูลของคุณจะเบาบางพอคุณ
ได้รับเวลานี้คงสวยงาม

293
00:11:48,287 --> 00:11:50,620
แต่ทันทีที่คุณเริ่มต้น
รับองค์ประกอบมากขึ้นและมากขึ้น

294
00:11:50,620 --> 00:11:53,200
และเพียงแค่สถิติที่คุณจะได้รับ
ผู้คนมากขึ้นด้วยตัวอักษร

295
00:11:53,200 --> 00:11:56,030
เป็นชื่อหรือหนังสือของพวกเขา
B, มันอาจ

296
00:11:56,030 --> 00:11:57,900
ตกมาเป็นสิ่งที่มากขึ้นเชิงเส้น

297
00:11:57,900 --> 00:11:59,640
จึงไม่สมบูรณ์แบบเลยทีเดียว

298
00:11:59,640 --> 00:12:00,690
เพื่อให้เราสามารถทำดีกว่า

299
00:12:00,690 --> 00:12:03,210
>> ดีสิ่งที่เป็นของเรา
การแก้ปัญหาก่อนที่เมื่อเรา

300
00:12:03,210 --> 00:12:06,820
ต้องการที่จะมีชีวิตชีวามากกว่า
บางอย่างเช่นอาเรย์ได้รับอนุญาต?

301
00:12:06,820 --> 00:12:08,085

302
00:12:08,085 --> 00:12:08,960
ผู้ชม: [ไม่ได้ยิน]

303
00:12:08,960 --> 00:12:10,030
DAVID ลัน: เราไม่แนะนำอะไร?

304
00:12:10,030 --> 00:12:10,530
ใช่

305
00:12:10,530 --> 00:12:11,430
ดังนั้นรายการที่เชื่อมโยง

306
00:12:11,430 --> 00:12:14,430
ดีขอดูสิ่งที่เชื่อมโยง
รายการอาจจะทำเพื่อเราแทน

307
00:12:14,430 --> 00:12:17,630
ดีให้ฉันเสนอเราว่า
วาดภาพดังต่อไปนี้

308
00:12:17,630 --> 00:12:19,620
ขณะนี้เป็นที่แตกต่างกัน
ภาพจากตัวอย่าง

309
00:12:19,620 --> 00:12:24,750
จากข้อความที่แตกต่างกันในความเป็นจริงว่า
เป็นจริงโดยใช้อาร์เรย์ขนาด 31

310
00:12:24,750 --> 00:12:28,220
และผู้เขียนคนนี้เพียงแค่
ตัดสินใจที่จะสับสตริง

311
00:12:28,220 --> 00:12:32,430
ไม่ได้ขึ้นอยู่กับชื่อของบุคคล
แต่ขึ้นอยู่กับวันเกิดของพวกเขา

312
00:12:32,430 --> 00:12:35,680
โดยไม่คำนึงถึงของเดือนที่พวกเขาคิด
ถ้าคุณเกิดในวันแรกของเดือน

313
00:12:35,680 --> 00:12:39,580
หรือวันที่ 31 ของเดือนที่ผู้เขียน
จะสับขึ้นอยู่กับค่าที่

314
00:12:39,580 --> 00:12:44,154
เพื่อกระจายชื่อออกเล็กน้อย
มากกว่าเพียงแค่ 26 จุดที่อาจจะช่วยให้

315
00:12:44,154 --> 00:12:47,320
และบางทีมันอาจจะเป็นชุดที่น้อยมาก
กว่าจะมีตัวอักษรตัวอักษร

316
00:12:47,320 --> 00:12:50,236
เพราะแน่นอนอาจมี
ผู้คนจำนวนมากในโลกที่มีชื่อ

317
00:12:50,236 --> 00:12:54,020
เริ่มต้นด้วยกว่าแน่นอนว่า
บางตัวอักษรอื่น ๆ ของตัวอักษร

318
00:12:54,020 --> 00:12:56,380
ดังนั้นอาจจะเป็นเพียงเล็กน้อย
เครื่องแบบสมมติ

319
00:12:56,380 --> 00:12:58,640
กระจายสม่ำเสมอ
ของทารกในเดือน

320
00:12:58,640 --> 00:12:59,990
>> แต่แน่นอนนี้ยังคงไม่สมบูรณ์

321
00:12:59,990 --> 00:13:00,370
ใช่มั้ย?

322
00:13:00,370 --> 00:13:01,370
เรากำลังมีการชนกัน

323
00:13:01,370 --> 00:13:04,680
หลายคนในนี้
โครงสร้างข้อมูลยังคงอยู่

324
00:13:04,680 --> 00:13:08,432
มีวันเกิดเดียวกันอย่างน้อย
คุณโดยไม่คำนึงถึงเดือน

325
00:13:08,432 --> 00:13:09,640
แต่สิ่งที่ผู้เขียนได้ทำ?

326
00:13:09,640 --> 00:13:13,427
ดีก็ดูเหมือนว่าเรามีอาร์เรย์
อยู่ทางด้านซ้ายมือวาดในแนวตั้ง

327
00:13:13,427 --> 00:13:15,010
แต่นั่นเป็นเพียงการกระทำของศิลปิน

328
00:13:15,010 --> 00:13:18,009
มันไม่สำคัญว่าสิ่งที่ทิศทางที่คุณ
วาดอาร์เรย์ก็ยังคงอาร์เรย์

329
00:13:18,009 --> 00:13:20,225
สิ่งนี้เป็นอาร์เรย์ของเห็นได้ชัด?

330
00:13:20,225 --> 00:13:21,500
>> ผู้ชม: รายการที่เชื่อมโยง

331
00:13:21,500 --> 00:13:21,650
>> DAVID ลัน: ใช่

332
00:13:21,650 --> 00:13:23,490
ดูเหมือนว่าจะเป็น
อาร์เรย์ของรายการที่เชื่อมโยง

333
00:13:23,490 --> 00:13:26,490
ดังนั้นอีกครั้งไปยังจุดของการจัดเรียงนี้
ของการใช้โครงสร้างข้อมูลเหล่านี้

334
00:13:26,490 --> 00:13:28,550
เป็นส่วนประกอบให้มากขึ้น
การแก้ปัญหาที่น่าสนใจ

335
00:13:28,550 --> 00:13:30,862
คุณอย่างสามารถใช้
พื้นฐานเช่นอาร์เรย์

336
00:13:30,862 --> 00:13:33,320
แล้วนำสิ่งที่มากขึ้น
ที่น่าสนใจเช่นรายการที่เชื่อมโยง

337
00:13:33,320 --> 00:13:36,660
และแม้กระทั่งการรวมพวกเขาเป็นได้
โครงสร้างข้อมูลที่น่าสนใจอื่น ๆ อีกมากมาย

338
00:13:36,660 --> 00:13:39,630
และแน่นอนนี้จะเกินไป
จะเรียกว่าตารางแฮช,

339
00:13:39,630 --> 00:13:42,610
โดยอาร์เรย์เป็น
จริงๆตารางแฮช,

340
00:13:42,610 --> 00:13:45,600
แต่ตารางแฮชที่มี
เครือข่ายเพื่อที่จะพูด

341
00:13:45,600 --> 00:13:50,220
ที่สามารถเติบโตหรือหดตาม
จำนวนขององค์ประกอบที่คุณต้องการแทรก

342
00:13:50,220 --> 00:13:52,990
>> ตอนนี้ดังนั้นสิ่งที่
เวลาที่ใช้ตอนนี้หรือไม่

343
00:13:52,990 --> 00:13:58,030
ถ้าผมต้องการที่จะใส่คน
ที่มีวันเกิดเป็นวันที่ 31 ตุลาคม

344
00:13:58,030 --> 00:13:59,040
ที่เขาหรือเธอไป?

345
00:13:59,040 --> 00:14:00,530

346
00:14:00,530 --> 00:14:01,030
สิทธิ์ทั้งหมด

347
00:14:01,030 --> 00:14:02,819
ที่ด้านล่างสุดที่จะกล่าวว่าวันที่ 31

348
00:14:02,819 --> 00:14:03,610
และนั่นคือสิ่งที่สมบูรณ์แบบ

349
00:14:03,610 --> 00:14:05,060
นั่นเป็นครั้งอย่างต่อเนื่อง

350
00:14:05,060 --> 00:14:08,760
แต่ถ้าเราหาคนอื่น
ที่มีวันเกิดที่ให้มาดู

351
00:14:08,760 --> 00:14:10,950
เดือนตุลาคมพฤศจิกายน 31 ธันวาคม?

352
00:14:10,950 --> 00:14:12,790
อยู่ที่ไหนเขาหรือเธอจะไป?

353
00:14:12,790 --> 00:14:13,290
สิ่งเดียวกัน

354
00:14:13,290 --> 00:14:13,970
ขั้นตอนที่สองว่า

355
00:14:13,970 --> 00:14:15,303
ที่คงที่แม้ว่าไม่ได้หรือไม่

356
00:14:15,303 --> 00:14:16,360

357
00:14:16,360 --> 00:14:16,860
สิทธิ์ทั้งหมด

358
00:14:16,860 --> 00:14:17,840
ในขณะที่มันเป็น

359
00:14:17,840 --> 00:14:20,570
แต่ในกรณีทั่วไป
ผู้คนจำนวนมากที่เราเพิ่ม

360
00:14:20,570 --> 00:14:23,790
ความน่าจะเป็นเราจะ
ที่จะได้รับการชนกันมากขึ้น

361
00:14:23,790 --> 00:14:26,820
>> ขณะนี้เป็นเพียงเล็กน้อย
ดีกว่าเพราะในทางเทคนิค

362
00:14:26,820 --> 00:14:34,580
ตอนนี้กลุ่มของฉันอาจจะอยู่ใน
กรณีที่เลวร้ายนานแค่ไหน?

363
00:14:34,580 --> 00:14:38,890
ถ้าฉันใส่ n คนเข้ามามากขึ้น
โครงสร้างข้อมูลที่ซับซ้อน n คน

364
00:14:38,890 --> 00:14:41,080
ในกรณีที่เลวร้ายที่สุดมันจะเป็น n

365
00:14:41,080 --> 00:14:41,815
ทำไม?

366
00:14:41,815 --> 00:14:43,332
>> ผู้ชม: เพ​​ราะถ้าทุกคน
มีวันเกิดเดียวกัน

367
00:14:43,332 --> 00:14:44,545
พวกเขากำลังจะเป็นหนึ่งในสาย

368
00:14:44,545 --> 00:14:45,420
DAVID ลันเพอร์เฟ

369
00:14:45,420 --> 00:14:47,480
มันอาจจะประดิษฐ์เล็ก ๆ น้อย ๆ
แต่อย่างแท้จริงในกรณีที่เลวร้ายที่สุด

370
00:14:47,480 --> 00:14:50,117
ถ้าทุกคนมีวันเกิดเดียวกัน
ที่ได้รับปัจจัยการผลิตที่คุณมี

371
00:14:50,117 --> 00:14:51,950
คุณกำลังจะมี
ห่วงโซ่ยาวอย่างหนาแน่น

372
00:14:51,950 --> 00:14:54,241
และเพื่อให้คุณสามารถเรียกมันว่า
สับตาราง แต่จริงๆมัน

373
00:14:54,241 --> 00:14:56,810
เพียงแค่รายการที่เชื่อมโยงขนาดใหญ่ที่มี
เป็นจำนวนมากทั้งของพื้นที่ที่สูญเสียไป

374
00:14:56,810 --> 00:15:00,460
แต่โดยทั่วไปถ้าเราคิดว่า
อย่างน้อยวันเกิดเป็น uniform--

375
00:15:00,460 --> 00:15:01,750
และมันอาจจะไม่

376
00:15:01,750 --> 00:15:02,587
ฉันทำขึ้น

377
00:15:02,587 --> 00:15:04,420
แต่ถ้าเราคิดว่าสำหรับ
ประโยชน์ของการสนทนา

378
00:15:04,420 --> 00:15:07,717
ว่าพวกเขามีแล้วในทางทฤษฎีถ้า
นี้คือการแสดงในแนวตั้ง

379
00:15:07,717 --> 00:15:11,050
ของอาร์เรย์ที่ดีแล้วหวังว่าคุณ
จะได้รับกลุ่มที่มีคุณรู้ว่า

380
00:15:11,050 --> 00:15:15,880
ประมาณระยะเวลาเดียวกับที่แต่ละ
เหล่านี้แสดงให้เห็นถึงวันของเดือน

381
00:15:15,880 --> 00:15:19,930
>> ตอนนี้ถ้ามี 31 วันในเดือน,
นั่นหมายความว่าเวลาทำงานของฉันจริงๆ

382
00:15:19,930 --> 00:15:25,230
เป็น O ใหญ่ของ n กว่า 31 ซึ่ง
รู้สึกดีขึ้นกว่าที่เป็นเส้นตรง

383
00:15:25,230 --> 00:15:27,950
แต่สิ่งที่เป็นหนึ่งในของเรา
ภาระผูกพันสองสามสัปดาห์

384
00:15:27,950 --> 00:15:31,145
ที่ผ่านมาเมื่อใดก็ตามที่มันมาถึงการแสดง
เวลาทำงานของอัลกอริทึม?

385
00:15:31,145 --> 00:15:33,450

386
00:15:33,450 --> 00:15:35,190
เพียงมองไปที่คำสั่งซื้อสูง

387
00:15:35,190 --> 00:15:35,690
ใช่มั้ย?

388
00:15:35,690 --> 00:15:37,400
31 แน่นอนเป็นประโยชน์

389
00:15:37,400 --> 00:15:39,610
แต่นี้ยังคง O ใหญ่ของ n

390
00:15:39,610 --> 00:15:41,730
แต่หนึ่งในรูปแบบ
ของปัญหาการตั้งห้า

391
00:15:41,730 --> 00:15:43,950
เป็นไปได้ที่จะ
ยอมรับว่าอย่างแน่นอน

392
00:15:43,950 --> 00:15:47,320
asymptotically เหตุผล
โครงสร้างข้อมูลนี้

393
00:15:47,320 --> 00:15:50,470
ไม่ดีกว่าเพียงแค่
หนึ่งรายการที่เชื่อมโยงขนาดใหญ่

394
00:15:50,470 --> 00:15:53,550
และแน่นอนในกรณีที่เลวร้ายที่สุดนี้
ตารางแฮชอาจจะตกมาอยู่ในที่

395
00:15:53,550 --> 00:15:57,620
>> แต่ในโลกแห่งความจริงกับมนุษย์เรา
ที่แม็คเองหรือเครื่องคอมพิวเตอร์หรืออะไรก็ตาม

396
00:15:57,620 --> 00:16:01,240
และกำลังทำงานอยู่โลกแห่งความจริง
ซอฟแวร์กับข้อมูลจริง

397
00:16:01,240 --> 00:16:03,260
ซึ่งขั้นตอนวิธีที่คุณจะชอบ?

398
00:16:03,260 --> 00:16:09,180
หนึ่งที่ใช้ขั้นตอนปลายหรือ
หนึ่งที่จะใช้เวลา n หารด้วย 31 ขั้นตอน

399
00:16:09,180 --> 00:16:12,900
ที่จะหาชิ้นส่วนของข้อมูลบางส่วนหรือ
เพื่อค้นหาข้อมูลบางอย่าง?

400
00:16:12,900 --> 00:16:16,580
ผมหมายความว่าอย่าง 31 ทำให้
ความแตกต่างในโลกแห่งความจริง

401
00:16:16,580 --> 00:16:18,540
มันเป็น 31 ครั้งได้เร็วขึ้น

402
00:16:18,540 --> 00:16:20,880
และมนุษย์เราอย่างแน่นอน
จะขอบคุณที่

403
00:16:20,880 --> 00:16:23,004
>> เพื่อตระหนักถึงขั้ว
ระหว่างมีจริง

404
00:16:23,004 --> 00:16:25,920
พูดคุยเกี่ยวกับสิ่งที่ในทางทฤษฎี
และในเชิงเส้นที่แน่นอน

405
00:16:25,920 --> 00:16:28,760
มีค่าที่เราได้เห็น
แต่ในโลกแห่งความเป็นจริง

406
00:16:28,760 --> 00:16:32,930
ถ้าคุณดูแลเกี่ยวกับการเพียงแค่การทำ
ความสุขของมนุษย์สำหรับปัจจัยการผลิตทั่วไป

407
00:16:32,930 --> 00:16:36,010
คุณเป็นอย่างดีอาจต้องการที่จะยอมรับ
ความจริงที่ว่าใช่นี้เป็นเชิงเส้น

408
00:16:36,010 --> 00:16:38,360
แต่มันก็เป็น 31 ครั้งได้เร็วขึ้น
กว่าเส้นอาจจะมี

409
00:16:38,360 --> 00:16:41,610
และยังดีกว่าเราไม่เพียงแค่ต้อง
ทำอะไรโดยพลการเช่นวันเกิด,

410
00:16:41,610 --> 00:16:44,030
เราสามารถใช้จ่ายเล็ก ๆ น้อย ๆ
เวลาและความฉลาด

411
00:16:44,030 --> 00:16:47,140
และคิดเกี่ยวกับสิ่งที่เราอาจจะทำ
ชื่อของบุคคลและอาจจะ

412
00:16:47,140 --> 00:16:50,130
วันเกิดของพวกเขาที่จะรวมเหล่านั้น
ส่วนผสมที่จะคิดออกบางสิ่งบางอย่าง

413
00:16:50,130 --> 00:16:52,720
ที่เป็นจริงมากขึ้น
สม่ำเสมอและหยักน้อย

414
00:16:52,720 --> 00:16:56,250
จึงจะพูดกว่าภาพนี้
นี้แสดงให้เห็นว่ามันอาจจะ

415
00:16:56,250 --> 00:16:57,750
วิธีการที่เราสามารถดำเนินการนี​​้ในรหัส?

416
00:16:57,750 --> 00:17:00,280
ดีให้ฉันเสนอเราว่า
เพียงแค่ขอยืมไวยากรณ์บางอย่างที่เราได้

417
00:17:00,280 --> 00:17:01,799
ใช้กี่ครั้งป่านนี้

418
00:17:01,799 --> 00:17:03,590
และฉันจะต้องกำหนด
โหนดที่อีกครั้ง

419
00:17:03,590 --> 00:17:06,812
เป็นคำทั่วไปสำหรับเพียงบางส่วน
ภาชนะสำหรับโครงสร้างข้อมูลบางส่วน

420
00:17:06,812 --> 00:17:09,020
ฉันจะเสนอว่า
สตริงเป็นไปในที่นั่น

421
00:17:09,020 --> 00:17:11,369
แต่เรากำลังจะเริ่มต้นการ
ผู้ที่ล้อการฝึกอบรมออกตอนนี้

422
00:17:11,369 --> 00:17:13,230
>> ไม่มีห้องสมุด CS50 เพิ่มเติม
จริงๆถ้าคุณต้องการ

423
00:17:13,230 --> 00:17:15,230
ที่จะใช้สำหรับขั้นสุดท้ายของคุณ
โครงการซึ่งเป็นเรื่องปกติ

424
00:17:15,230 --> 00:17:18,569
แต่ตอนนี้เรากำลังจะดึงกลับมา
ผ้าม่านและบอกว่ามันเป็นเพียงแค่ดาวถ่าน

425
00:17:18,569 --> 00:17:22,069
ดังนั้นคำว่ามีเป็นไปได้
ชื่อของบุคคลในคำถาม

426
00:17:22,069 --> 00:17:25,079
และตอนนี้ฉันมีการเชื่อมโยง
ที่นี่ไปยังโหนดถั​​ดไป

427
00:17:25,079 --> 00:17:28,170
เพื่อที่ว่าเหล่านี้เป็นตัวแทน
แต่ละโหนด

428
00:17:28,170 --> 00:17:30,950
ในห่วงโซ่ที่อาจ
ของรายการที่เชื่อมโยง

429
00:17:30,950 --> 00:17:34,090
>> และตอนนี้ฉันจะประกาศ
ตารางแฮชของตัวเอง?

430
00:17:34,090 --> 00:17:36,660
ผมไม่ประกาศโครงสร้างทั้งหมดนี้ได้อย่างไร

431
00:17:36,660 --> 00:17:40,960
ดีจริงๆเหมือนผมใช้ตัวชี้
เพียงแค่องค์ประกอบแรกของรายการ

432
00:17:40,960 --> 00:17:44,510
ก่อนที่จะคล้าย ๆ ฉันสามารถเพียงกล่าวว่า
ผมเพียงแค่ต้องพวงของตัวชี้

433
00:17:44,510 --> 00:17:46,270
ที่จะใช้ตารางแฮชทั้งหมดนี้

434
00:17:46,270 --> 00:17:49,484
ฉันจะมีอาร์เรย์
เรียกว่าตารางสำหรับตารางแฮช

435
00:17:49,484 --> 00:17:50,900
มันเป็นไปได้ของความจุขนาด

436
00:17:50,900 --> 00:17:52,525
นั่นเป็นวิธีที่หลายองค์ประกอบสามารถใส่ในนั้น

437
00:17:52,525 --> 00:17:56,180
และแต่ละองค์ประกอบเหล่านั้นในเรื่องนี้
อาร์เรย์เป็นไปได้ที่ดาวโหนด

438
00:17:56,180 --> 00:17:56,810
ทำไม?

439
00:17:56,810 --> 00:18:00,160
ดีต่อภาพนี้สิ่งที่ฉัน
การดำเนินการตารางแฮชเป็น

440
00:18:00,160 --> 00:18:04,330
ได้อย่างมีประสิทธิภาพในการเริ่มต้นเป็นเพียง
แถวนี้ที่เราได้วาดในแนวตั้ง

441
00:18:04,330 --> 00:18:06,820
แต่ละสี่เหลี่ยมที่มี
แสดงให้เห็นถึงตัวชี้

442
00:18:06,820 --> 00:18:09,170
ว่าคนที่มีความทับ
ผ่านพวกเขาเป็นเพียง null

443
00:18:09,170 --> 00:18:11,410
และคนที่มี
ลูกศรไปทางขวา

444
00:18:11,410 --> 00:18:16,140
เป็นตัวชี้ไปยังโหนดที่เกิดขึ้นจริงที่เกิดขึ้นจริง
เพราะฉะนั้นจุดเริ่มต้นของรายการที่เชื่อมโยง

445
00:18:16,140 --> 00:18:19,050
>> ดังนั้นที่นี่ก็คือวิธีการที่เราอาจจะ
ใช้ตารางแฮชที่

446
00:18:19,050 --> 00:18:21,580
ดำเนินการผูกมัดแยกต่างหาก

447
00:18:21,580 --> 00:18:22,840
ตอนนี้เราสามารถทำดีกว่า

448
00:18:22,840 --> 00:18:25,632
สิทธิทั้งหมดที่ฉันสัญญาว่าครั้งสุดท้ายที่
เราสามารถประสบความสำเร็จอย่างต่อเนื่องตลอดเวลา

449
00:18:25,632 --> 00:18:27,381
และชนิดของฉันให้คุณ
เวลาคงที่นี่

450
00:18:27,381 --> 00:18:29,850
แต่แล้วก็กล่าวว่าไม่ได้จริงๆ
เวลาคงเพราะมันยังคง

451
00:18:29,850 --> 00:18:31,890
ขึ้นอยู่กับทั้งหมด
จำนวนขององค์ประกอบ

452
00:18:31,890 --> 00:18:34,500
คุณกำลังป้อนเข้าไปใน
โครงสร้างข้อมูล

453
00:18:34,500 --> 00:18:35,980
แต่สมมติว่าเราทำอย่างนี้

454
00:18:35,980 --> 00:18:39,550
ผมขอกลับไปที่หน้าจอมากกว่าที่นี่

455
00:18:39,550 --> 00:18:44,520
ให้ฉันยังโครงการนี​​้ขึ้นที่นี่ชัดเจน
หน้าจอและคิดว่าฉันทำอย่างนี้

456
00:18:44,520 --> 00:18:49,300
สมมติว่าผมต้องการที่จะใส่ชื่อ
Daven ในในโครงสร้างข้อมูลของฉัน

457
00:18:49,300 --> 00:18:52,100
>> ดังนั้นผมจึงต้องการแทรกสตริง
Daven เป็นโครงสร้างข้อมูล

458
00:18:52,100 --> 00:18:54,370
จะทำอย่างไรถ้าฉันไม่ได้ใช้
สับตาราง แต่ฉันจะใช้

459
00:18:54,370 --> 00:18:56,980
สิ่งที่มากขึ้นต้นไม้
เหมือนต้นไม้ครอบครัวที่

460
00:18:56,980 --> 00:18:59,670
คุณมีรากบางส่วนที่
โหนดด้านบนแล้วและใบ

461
00:18:59,670 --> 00:19:01,440
ที่ไปลงและขาออก

462
00:19:01,440 --> 00:19:04,450
สมมติว่าแล้วผมว่า
ต้องการแทรก Daven ของ

463
00:19:04,450 --> 00:19:06,430
เป็นสิ่งที่เป็นอยู่ในปัจจุบันรายการที่ว่างเปล่า

464
00:19:06,430 --> 00:19:09,780
ฉันจะทำต่อไปนี้: ฉัน
จะสร้างโหนดในครอบครัวนี้

465
00:19:09,780 --> 00:19:15,170
ต้นไม้โครงสร้างข้อมูลที่มีลักษณะ
เล็ก ๆ น้อย ๆ เช่นนี้ซึ่งแต่ละ

466
00:19:15,170 --> 00:19:19,640
รูปสี่เหลี่ยมได้สมมุติว่า
สำหรับตอนนี้ 26 องค์ประกอบในนั้น

467
00:19:19,640 --> 00:19:21,650
และแต่ละเซลล์
ในอาร์เรย์นี้จะ

468
00:19:21,650 --> 00:19:23,470
เพื่อเป็นตัวแทนของตัวอักษร

469
00:19:23,470 --> 00:19:28,190
>> โดยเฉพาะผมจะรักษา
นี้แล้ว B แล้ว C, D แล้ว,

470
00:19:28,190 --> 00:19:29,310
หนึ่งที่นี่

471
00:19:29,310 --> 00:19:32,940
ดังนั้นนี้เป็นไปอย่างมีประสิทธิภาพ
เป็นตัวแทนของตัวอักษรที่ดี

472
00:19:32,940 --> 00:19:36,040
แต่การที่จะใส่ทั้งหมดของ Daven ของ
ชื่อที่ฉันต้องทำมากขึ้นอีกนิด

473
00:19:36,040 --> 00:19:37,840
ดังนั้นฉันแรกจะสับจึงจะพูด

474
00:19:37,840 --> 00:19:41,049
ฉันจะไปดูที่ตัวอักษรตัวแรก
ใน Daven ซึ่งจะเห็นได้ชัด D,

475
00:19:41,049 --> 00:19:42,840
และฉันจะจัดสรร
โหนดที่มีลักษณะ

476
00:19:42,840 --> 00:19:45,570
เหมือนเจ้านี่สี่เหลี่ยมผืนผ้าขนาดใหญ่ขนาดใหญ่
พอที่จะพอดีกับตัวอักษรทั้ง

477
00:19:45,570 --> 00:19:47,140
>> ตอนนี้ D จะทำ

478
00:19:47,140 --> 00:19:49,720
ตอนนี้ A. D-A-V-E-N เป​​็นเป้าหมาย

479
00:19:49,720 --> 00:19:51,220
ดังนั้นตอนนี้สิ่งที่ผมจะทำคือ

480
00:19:51,220 --> 00:19:54,027
ทันทีที่ผมเริ่ม D แจ้งให้ทราบล่วงหน้า
มีตัวชี้ไม่มี

481
00:19:54,027 --> 00:19:56,860
มันเป็นค่าขยะในขณะนี้
หรือฉันอาจจะเริ่มต้นมันเป็นโมฆะ

482
00:19:56,860 --> 00:19:59,630
แต่ให้ฉันเก็บไปด้วย
ความคิดของการสร้างต้นไม้นี้

483
00:19:59,630 --> 00:20:04,260
ผมขอจัดสรรอีกหนึ่งของเหล่านี้
โหนดที่มี 26 องค์ประกอบในนั้น

484
00:20:04,260 --> 00:20:05,150
>> และคุณรู้อะไรไหม?

485
00:20:05,150 --> 00:20:09,130
ถ้านี้เป็นเพียงโหนดในหน่วยความจำที่
ฉันสร้างขึ้นด้วย malloc ใช้ struct

486
00:20:09,130 --> 00:20:11,240
ในขณะที่เราจะเห็นทันทีที่
ฉันจะทำเจ้านี่

487
00:20:11,240 --> 00:20:14,450
ฉันจะวาดล​​ูกศรจาก
สิ่งที่เป็นตัวแทน D ลง

488
00:20:14,450 --> 00:20:15,860
ไปยังโหนดใหม่นี้

489
00:20:15,860 --> 00:20:19,240
และตอนนี้เป็นครั้งแรกต่อไป
ตัวอักษรที่อยู่ในชื่อ Daven ของ

490
00:20:19,240 --> 00:20:24,150
V-- D-A-V-- ฉันจะไปข้างหน้า
และวาดโหนดอื่นเช่นนี้

491
00:20:24,150 --> 00:20:30,150
โดยองค์ประกอบ V ที่นี่ซึ่ง
เราจะวาด instance-- ขออภัย

492
00:20:30,150 --> 00:20:31,020
เราจะไม่วาดมี

493
00:20:31,020 --> 00:20:31,936
มันจะไปที่นี่

494
00:20:31,936 --> 00:20:32,890

495
00:20:32,890 --> 00:20:35,712
>> จากนั้นเรากำลังจะไป
พิจารณานี้จะ V.

496
00:20:35,712 --> 00:20:44,920
แล้วลงที่นี่เรากำลังจะดัชนี
ลดลงจาก V เป็นสิ่งที่เราจะพิจารณาอี

497
00:20:44,920 --> 00:20:50,100
และจากที่นี่เรากำลังจะไป
ไปมีหนึ่งโหนดเหล่านี้ที่นี่

498
00:20:50,100 --> 00:20:52,930
และตอนนี้เรามีคำถามที่จะตอบ

499
00:20:52,930 --> 00:20:57,840
ฉันต้องการที่จะแสดงให้เห็นว่าอย่างใด
เราอยู่ที่ปลายสาย Daven

500
00:20:57,840 --> 00:20:59,490
ดังนั้นผมก็สามารถปล่อยให้มันเป็นโมฆะ

501
00:20:59,490 --> 00:21:02,670
>> แต่สิ่งที่ถ้าเรามี Daven ของ
ชื่อเต็มด้วยซึ่ง

502
00:21:02,670 --> 00:21:04,280
คือในขณะที่เราได้กล่าวว่าดาเวนพอร์ต?

503
00:21:04,280 --> 00:21:06,970
ดังนั้นสิ่งที่ถ้าเป็น Daven
จริงย่อย,

504
00:21:06,970 --> 00:21:08,960
คำนำหน้าของสตริงนานมาก?

505
00:21:08,960 --> 00:21:11,450
เราก็ไม่สามารถไปอย่างถาวร
พูดอะไรที่เป็นไป

506
00:21:11,450 --> 00:21:14,410
ไปที่นั่นเพราะเราสามารถทำได้
ไม่เคยใส่คำเหมือนดาเวนพอร์ต

507
00:21:14,410 --> 00:21:15,840
เป็นโครงสร้างข้อมูล

508
00:21:15,840 --> 00:21:19,560
>> ดังนั้นสิ่งที่เราสามารถทำแทนเป็น
ปฏิบัติต่อกันขององค์ประกอบเหล่านี้

509
00:21:19,560 --> 00:21:22,170
ขณะที่อาจจะมีสอง
องค์ประกอบภายในของพวกเขา

510
00:21:22,170 --> 00:21:24,810
หนึ่งคือตัวชี้จริง
ขณะที่ฉันได้ทำ

511
00:21:24,810 --> 00:21:27,100
ดังนั้นแต่ละกล่องเหล่านี้
ไม่ได้เป็นเพียงหนึ่งเซลล์

512
00:21:27,100 --> 00:21:29,855
แต่ถ้าด้านบน
one-- หนึ่งด้านล่างของ

513
00:21:29,855 --> 00:21:32,230
จะเป็นโมฆะเพราะ
ไม่มีหนังสือเพียง แต่

514
00:21:32,230 --> 00:21:34,197
ถ้าหนึ่งด้านบน
บางค่าพิเศษ?

515
00:21:34,197 --> 00:21:36,530
และมันจะเป็นเพียงเล็กน้อย
ยากที่จะวาดมันขนาดนี้

516
00:21:36,530 --> 00:21:38,130
แต่คิดว่ามันเป็นเพียงเครื่องหมาย

517
00:21:38,130 --> 00:21:38,920
ตรวจสอบ

518
00:21:38,920 --> 00:21:44,230
D-A-V-E-N เป​​็นสตริง
ในโครงสร้างของข้อมูลนี้

519
00:21:44,230 --> 00:21:48,350
>> ในขณะเดียวกันถ้าผมมีพื้นที่มากขึ้น
ที่นี่ฉันจะทำ P-O-R-T,

520
00:21:48,350 --> 00:21:52,650
และฉันจะทำให้การตรวจสอบในโหนด
ที่มีตัวอักษร T ที่ท้ายสุด

521
00:21:52,650 --> 00:21:55,460
ดังนั้นนี่คืออย่างหนาแน่น
ซับซ้อนมองโครงสร้างข้อมูล

522
00:21:55,460 --> 00:21:57,210
และเขียนด้วยลายมือของฉัน
แน่นอนไม่ได้ช่วย

523
00:21:57,210 --> 00:22:00,043
แต่ถ้าผมอยากจะใส่อะไรบางอย่าง
อื่นพิจารณาสิ่งที่เราจะทำ

524
00:22:00,043 --> 00:22:03,370
ถ้าเราต้องการที่จะนำดาวิด
เราจะทำตามตรรกะเดียวกัน D-A-V,

525
00:22:03,370 --> 00:22:08,802
แต่ตอนนี้ผมจะชี้ให้ในครั้งต่อไป
องค์ประกอบไม่ได้มาจาก E แต่จากที่ฉันจะดี

526
00:22:08,802 --> 00:22:10,760
ดังนั้นจึงมีความเป็นไปได้
โหนดในต้นไม้ต้นนี้

527
00:22:10,760 --> 00:22:12,325
เรากำลังจะมีการเรียก malloc เพิ่มเติม

528
00:22:12,325 --> 00:22:14,700
แต่ฉันไม่ต้องการที่จะให้
รับประทานอาหารที่สมบูรณ์ของภาพนี้

529
00:22:14,700 --> 00:22:17,710
จึงขอแทนที่จะมองไปที่หนึ่ง
ที่ถูกก่อนกำหนด

530
00:22:17,710 --> 00:22:21,810
เช่นนี้ไม่ได้มีจุด, จุด,
จุด แต่อาร์เรย์ยากเพียงแค่

531
00:22:21,810 --> 00:22:23,950
แต่แต่ละโหนด
ในต้นไม้ขึ้นที่นี่

532
00:22:23,950 --> 00:22:26,700
แสดงให้เห็นถึง thing-- เดียวกัน
อาเรย์เรย์ขนาด 26

533
00:22:26,700 --> 00:22:28,860
>> หรือถ้าเราต้องการที่จะ
ที่เหมาะสมจริงๆตอนนี้สิ่งที่

534
00:22:28,860 --> 00:22:30,790
ถ้าชื่อของใครบางคนเป็น
เครื่องหมายวรรคตอนให้

535
00:22:30,790 --> 00:22:35,560
สมมติว่าแต่ละโหนดจริงมี
เช่น 27 ดัชนีในมันไม่ใช่แค่ 26

536
00:22:35,560 --> 00:22:42,020
ดังนั้นในตอนนี้จะเป็นข้อมูลที่
โครงสร้างที่เรียกว่า trie-- T-R-I-E

537
00:22:42,020 --> 00:22:46,120
Trie ซึ่งเป็นที่คาดคะเน
ในอดีตชื่อฉลาดสำหรับต้นไม้

538
00:22:46,120 --> 00:22:49,040
ที่เหมาะสำหรับ
การเรียกที่แน่นอน

539
00:22:49,040 --> 00:22:50,870
ถูกสะกดด้วย I-E จึง Trie

540
00:22:50,870 --> 00:22:52,710
แต่ที่เป็นประวัติศาสตร์ของ Trie

541
00:22:52,710 --> 00:22:55,860
>> ดังนั้น Trie ข้อมูลต้นไม้เช่นนี้
โครงสร้างเช่นต้นไม้ครอบครัว

542
00:22:55,860 --> 00:22:57,510
ในท้ายที่สุดว่ามีพฤติกรรมเช่นนั้น

543
00:22:57,510 --> 00:23:00,890
และนี่เป็นเพียงตัวอย่างของอีก
ทั้งกลุ่มของชื่อของคนอื่น

544
00:23:00,890 --> 00:23:03,540
แต่คำถามนี้
ที่อยู่ในมือคือสิ่งที่มี

545
00:23:03,540 --> 00:23:08,070
เราได้รับโดยการแนะนำเนื้อหาที่มากขึ้น
โครงสร้างข้อมูลที่ซับซ้อนและหนึ่ง

546
00:23:08,070 --> 00:23:09,870
ตรงไปตรงมาที่ใช้หน่วยความจำมาก

547
00:23:09,870 --> 00:23:11,703
>> เพราะถึงแม้,
ในขณะที่ฉันเท่านั้น

548
00:23:11,703 --> 00:23:15,050
ใช้ตัวชี้ D'และ
และ V แ​​ละ Es และ NS,

549
00:23:15,050 --> 00:23:16,700
ฉันเสีย heck ของมากของหน่วยความจำ

550
00:23:16,700 --> 00:23:18,030

551
00:23:18,030 --> 00:23:22,660
แต่ที่ผมใช้ทรัพยากรหนึ่ง
ฉันมักจะได้รับกลับทำอีก

552
00:23:22,660 --> 00:23:26,020
ดังนั้นถ้าผมใช้พื้นที่มากขึ้น
สิ่งที่อาจจะเป็นความหวังหรือไม่

553
00:23:26,020 --> 00:23:27,407
ที่ฉันใช้จ่ายน้อยอะไร?

554
00:23:27,407 --> 00:23:28,240
ผู้ชม: ใช้เวลาน้อยลง

555
00:23:28,240 --> 00:23:28,990
DAVID ลัน: เวลา

556
00:23:28,990 --> 00:23:30,320
ตอนนี้ทำไมที่อาจจะมี?

557
00:23:30,320 --> 00:23:33,880
ดีสิ่งที่เป็นแทรก
เวลาในแง่ของ O ขนาดใหญ่ในขณะนี้

558
00:23:33,880 --> 00:23:37,660
ชื่อเหมือน Daven
หรือหนังสือหรือดาวิด

559
00:23:37,660 --> 00:23:39,340
ดี Daven เป็นห้าขั้นตอน

560
00:23:39,340 --> 00:23:42,350
ดาเวนพอร์ตจะเป็นเก้าขั้นตอน
ดังนั้นมันจะเป็นไม่กี่ขั้นตอนมากขึ้น

561
00:23:42,350 --> 00:23:44,250
เดวิดจะเป็นห้าขั้นตอนเป็นอย่างดี

562
00:23:44,250 --> 00:23:47,230
ดังนั้นผู้ที่เป็นรูปธรรม
ตัวเลข แต่ก็มี

563
00:23:47,230 --> 00:23:49,550
ขอบเขตบน
ความยาวของชื่อของใครบางคน

564
00:23:49,550 --> 00:23:52,240
และแน่นอนในปัญหา
ชุดห้าสเปค

565
00:23:52,240 --> 00:23:54,050
เรากำลังจะนำเสนอ
ว่ามันเป็นบางสิ่งบางอย่าง

566
00:23:54,050 --> 00:23:55,470
ที่ 40 บางแปลกตัวอักษร

567
00:23:55,470 --> 00:23:58,180
>> แนบเนียนไม่มีใครมี
ชื่อยาวเพียบ

568
00:23:58,180 --> 00:24:01,542
ซึ่งเป็นที่จะบอกว่าความยาวของ
ชื่อหรือความยาวของสตริงที่เราอาจจะ

569
00:24:01,542 --> 00:24:03,750
มีบางรัฐ
โครงสร้างเป็น arguably อะไร?

570
00:24:03,750 --> 00:24:05,550

571
00:24:05,550 --> 00:24:06,250
มันเป็นค่าคงที่

572
00:24:06,250 --> 00:24:06,430
ใช่มั้ย?

573
00:24:06,430 --> 00:24:09,310
มันอาจจะเป็นค่าคงที่ขนาดใหญ่เช่น
40 บางสิ่งบางอย่าง แต่มันเป็นค่าคงที่

574
00:24:09,310 --> 00:24:13,752
และมีการพึ่งพาไม่กี่
ชื่ออื่น ๆ ที่มีอยู่ในโครงสร้างของข้อมูลนี้

575
00:24:13,752 --> 00:24:15,460
ในคำอื่น ๆ ถ้าฉัน
ตอนนี้อยากจะใส่

576
00:24:15,460 --> 00:24:20,540
โคลทันหรือกาเบรียลหรือร็อบหรือ Zamyla หรือ
อลิสันหรือเบลินดาหรือชื่ออื่น ๆ

577
00:24:20,540 --> 00:24:23,940
จากพนักงานที่เป็นข้อมูลนี้
โครงสร้างเป็นเวลาการทำงาน

578
00:24:23,940 --> 00:24:26,750
ใส่ชื่ออื่น ๆ
จะเป็นที่รับผลกระทบ

579
00:24:26,750 --> 00:24:30,220
โดยองค์ประกอบอื่น ๆ จำนวนที่จะ
ในโครงสร้างข้อมูลอยู่แล้ว?

580
00:24:30,220 --> 00:24:31,040
มันไม่ใช่

581
00:24:31,040 --> 00:24:31,540
ใช่มั้ย?

582
00:24:31,540 --> 00:24:36,150
เพราะเราได้อย่างมีประสิทธิภาพโดยใช้
ตารางแฮชนี้หลายชั้น

583
00:24:36,150 --> 00:24:38,280
และเวลาในการทำงานของ
ใด ๆ ของการดำเนินงานเหล่านี้

584
00:24:38,280 --> 00:24:41,510
ไม่ได้ขึ้นอยู่กับจำนวนของ
องค์ประกอบที่มีอยู่ในโครงสร้างข้อมูล

585
00:24:41,510 --> 00:24:43,090
หรือที่ในที่สุดก็จะ
ที่จะอยู่ในโครงสร้างข้อมูล

586
00:24:43,090 --> 00:24:44,714
แต่อยู่กับความยาวของสิ่งเฉพาะ?

587
00:24:44,714 --> 00:24:46,500

588
00:24:46,500 --> 00:24:49,200
>> สตริงเป็น
แทรกซึ่งจะทำให้

589
00:24:49,200 --> 00:24:52,580
นี้คง asymptotically
O ใหญ่ time-- หนึ่ง

590
00:24:52,580 --> 00:24:54,720
และตรงไปตรงมาเพียงใน
โลกแห่งความจริงนี้

591
00:24:54,720 --> 00:24:58,380
หมายถึงการใส่ชื่อ Daven ใช้เวลา
เช่นห้าขั้นตอนหรือหนังสือเก้า

592
00:24:58,380 --> 00:25:00,100
ขั้นตอนหรือเดวิดห้าขั้นตอน

593
00:25:00,100 --> 00:25:03,071
นั่นคือสาปสวยครั้งที่ทำงานขนาดเล็ก

594
00:25:03,071 --> 00:25:05,320
และแน่นอนว่าเป็นมาก
สิ่งที่ดีโดยเฉพาะอย่างยิ่งเมื่อ

595
00:25:05,320 --> 00:25:08,126
มันไม่ได้ขึ้นอยู่กับทั้งหมด
จำนวนขององค์ประกอบในการมี

596
00:25:08,126 --> 00:25:10,500
ดังนั้นวิธีที่เราอาจดำเนินการนี​​้
ชนิดของโครงสร้างในรหัส?

597
00:25:10,500 --> 00:25:12,900
มันเป็นเรื่องเล็ก ๆ น้อย ๆ มากขึ้น
ที่ซับซ้อน แต่ยังคงเป็น

598
00:25:12,900 --> 00:25:15,050
เพียงแค่การประยุกต์ใช้
หน่วยการสร้างพื้นฐาน

599
00:25:15,050 --> 00:25:17,830
ฉันจะกำหนด
เราโหนดดังต่อไปนี้:

600
00:25:17,830 --> 00:25:21,100
บูลเรียกว่า word-- นี้
อาจจะเรียกว่าอะไร

601
00:25:21,100 --> 00:25:23,970
แต่บูลหมายถึง
สิ่งที่ฉันเข้ามาเป็นเครื่องหมาย

602
00:25:23,970 --> 00:25:24,490
ใช่

603
00:25:24,490 --> 00:25:26,720
นี่คือจุดสิ้นสุดของสตริง
ในโครงสร้างของข้อมูลนี้

604
00:25:26,720 --> 00:25:30,702
>> และแน่นอนดาวโหนด
มีจะหมายถึงเด็ก

605
00:25:30,702 --> 00:25:32,410
และแน่นอนเช่นเดียวกับ
ต้นไม้ครอบครัวของคุณ

606
00:25:32,410 --> 00:25:34,370
จะพิจารณาโหนด
ที่แขวนออก

607
00:25:34,370 --> 00:25:36,920
ของด้านล่างของผู้ปกครองบางส่วน
องค์ประกอบที่จะเป็นเด็ก

608
00:25:36,920 --> 00:25:40,510
และเพื่อให้เด็กเป็นไปได้
เป็นอาร์เรย์ของ 27 คนที่ 27

609
00:25:40,510 --> 00:25:41,680
เป็นเพียงสำหรับ apostrophe

610
00:25:41,680 --> 00:25:43,390
เรากำลังจะไปค้นหาที่พัก
กรณีพิเศษที่

611
00:25:43,390 --> 00:25:45,400
เพื่อให้คุณสามารถมีบางอย่าง
ชื่อที่มีเครื่องหมาย

612
00:25:45,400 --> 00:25:47,399
แม้อาจจะยัติภังค์ควร
ไปในนั้น แต่คุณจะ

613
00:25:47,399 --> 00:25:50,330
เห็นใน P ชุด 5 เราดูแลเท่านั้น
เกี่ยวกับตัวอักษรและเครื่องหมาย

614
00:25:50,330 --> 00:25:52,990
>> แล้วอย่างไรคุณเป็นตัวแทนของ
โครงสร้างข้อมูลของตัวเอง?

615
00:25:52,990 --> 00:25:56,454
คุณจะเป็นตัวแทนของราก
ของ Trie นี้เพื่อที่จะพูด?

616
00:25:56,454 --> 00:25:59,620
ดีเช่นเดียวกับรายการที่เชื่อมโยงคุณ
ต้องชี้ไปยังองค์ประกอบแรก

617
00:25:59,620 --> 00:26:04,270
ด้วย Trie คุณก็จำเป็นต้องใช้
ตัวชี้ไปยังรากของ Trie นี้

618
00:26:04,270 --> 00:26:07,290
และจากนั้นคุณสามารถสับ
วิธีการของคุณลงลึกและลึก

619
00:26:07,290 --> 00:26:10,460
ทุกโหนดอื่น ๆ ในโครงสร้าง

620
00:26:10,460 --> 00:26:13,440
ดังนั้นเพียงแค่มีความสามารถนี้
เราเป็นตัวแทน struct ที่

621
00:26:13,440 --> 00:26:15,877
>> ตอนนี้ Meanwhile-- โอ้คำถาม

622
00:26:15,877 --> 00:26:17,220
>> ผู้ชม: อะไรคือคำว่าบูล?

623
00:26:17,220 --> 00:26:20,490
>> DAVID ลัน: คำ Bool เป็น
เพียงแค่นี้ชาติ C

624
00:26:20,490 --> 00:26:22,920
สิ่งที่ผมอธิบาย
ในกล่องที่นี่เมื่อนี้

625
00:26:22,920 --> 00:26:26,000
ผมเริ่มแยกแต่ละ
องค์ประกอบของอาเรย์เป็นสองชิ้น

626
00:26:26,000 --> 00:26:27,600
หนึ่งคือตัวชี้ไปยังโหนดถั​​ดไป

627
00:26:27,600 --> 00:26:30,280
อื่น ๆ ที่จะต้องมี
สิ่งที่ต้องการกล่องกาเครื่องหมาย

628
00:26:30,280 --> 00:26:33,770
จะบอกว่าใช่มี
คำที่ลงท้าย Daven ที่นี่

629
00:26:33,770 --> 00:26:35,610
เพราะเราไม่ต้องการ
ในขณะที่เดฟ

630
00:26:35,610 --> 00:26:39,320
>> แม้ว่าเดฟเป็นไปได้
คำที่ถูกต้องเขาก็ไม่ได้อยู่ใน Trie

631
00:26:39,320 --> 00:26:39,830
ยัง

632
00:26:39,830 --> 00:26:40,950
และ D ไม่ใช่คำ

633
00:26:40,950 --> 00:26:42,770
และ D-ไม่ใช่คำหรือชื่อ

634
00:26:42,770 --> 00:26:45,020
ดังนั้นเครื่องหมาย
แสดงให้เห็นเพียงครั้งเดียวที่คุณ

635
00:26:45,020 --> 00:26:48,190
ตีโหนดนี้เป็น
เส้นทางก่อนหน้านี้ของตัวละคร

636
00:26:48,190 --> 00:26:50,700
จริงสตริงที่คุณใส่

637
00:26:50,700 --> 00:26:53,660
ดังนั้นนั่นคือทั้งหมดที่บูล
มีการทำสำหรับเรา

638
00:26:53,660 --> 00:26:55,500
>> ใด ๆ คำถามอื่น ๆ ที่พยายาม?

639
00:26:55,500 --> 00:26:56,215
ใช่

640
00:26:56,215 --> 00:26:58,035
>> ผู้ชม: การทับซ้อนคืออะไร?

641
00:26:58,035 --> 00:26:59,945
สิ่งที่ถ้าคุณมีเดฟและ Daven?

642
00:26:59,945 --> 00:27:00,820
DAVID ลันเพอร์เฟ

643
00:27:00,820 --> 00:27:02,580
สิ่งที่ถ้าคุณมีเดฟและ Daven?

644
00:27:02,580 --> 00:27:06,240
ดังนั้นหากเราแทรกบอกชื่อเล่น
สำหรับ David-- Dave-- D-A-V-E?

645
00:27:06,240 --> 00:27:07,370

646
00:27:07,370 --> 00:27:08,700
นี้เป็นจริงง่ายสุด

647
00:27:08,700 --> 00:27:10,325
ดังนั้นเราเพียง แต่จะใช้ขั้นตอนที่สี่

648
00:27:10,325 --> 00:27:11,042

649
00:27:11,042 --> 00:27:15,847
D-A-V-E และฉันทำในสิ่งที่ต้อง
ทำเมื่อผมกดที่โหนดที่สี่?

650
00:27:15,847 --> 00:27:16,680
เพียงแค่จะไปตรวจสอบ

651
00:27:16,680 --> 00:27:18,000
เราอยู่แล้วดีที่จะไป

652
00:27:18,000 --> 00:27:18,840
เสร็จแล้ว

653
00:27:18,840 --> 00:27:19,750
ขั้นตอนที่สี่

654
00:27:19,750 --> 00:27:21,590
เวลาคงที่ในเชิงเส้น

655
00:27:21,590 --> 00:27:26,300
และตอนนี้เราได้แสดงให้เห็นว่าทั้งเดฟ
และ Daven นี้จะมีอยู่ในโครงสร้าง

656
00:27:26,300 --> 00:27:27,710
ดังนั้นไม่ได้เป็นปัญหา

657
00:27:27,710 --> 00:27:30,200
และแจ้งให้ทราบว่าการปรากฏตัว
ของ Daven ไม่ได้ทำให้มัน

658
00:27:30,200 --> 00:27:34,750
ใช้เวลามากขึ้นหรือน้อยลง
เวลาสำหรับเดฟและในทางกลับกัน

659
00:27:34,750 --> 00:27:36,000
>> ดังนั้นอะไรที่สามารถตอนนี้เราจะทำอย่างไร

660
00:27:36,000 --> 00:27:40,680
เราได้ใช้คำอุปมานี้มาก่อน
ถาดที่เป็นตัวแทนของบางสิ่งบางอย่าง

661
00:27:40,680 --> 00:27:43,380
แต่มันกลับกลายเป็นว่า
สแต็คของถาดเป็นจริง

662
00:27:43,380 --> 00:27:47,187
ชี้ของข้อมูลนามธรรมอื่น
type-- ระดับโครงสร้างข้อมูลที่สูงขึ้น

663
00:27:47,187 --> 00:27:49,770
ว่าในท้ายที่สุดในวันนี้คือเพียงแค่
เช่นอาร์เรย์หรือรายการที่เชื่อมโยง

664
00:27:49,770 --> 00:27:50,970
หรือสิ่งที่โลกมากขึ้น

665
00:27:50,970 --> 00:27:53,270
แต่มันน่าสนใจมากขึ้น
แนวคิดแนวความคิด

666
00:27:53,270 --> 00:27:56,440
สแต็ค, เช่นนี้
ถาดที่นี่ในท้อง

667
00:27:56,440 --> 00:27:58,750
โดยทั่วไปจะเรียกว่า
เพียง that-- สแต็ค

668
00:27:58,750 --> 00:28:02,540
>> และในรูปแบบของโครงสร้างข้อมูลนี้
คุณมีสอง operations--

669
00:28:02,540 --> 00:28:05,880
คุณมีหนึ่งผลักดันเรียกร้องให้
เพิ่มสิ่งที่จะแตก

670
00:28:05,880 --> 00:28:08,320
เหมือนกับการใส่ถาดอื่น
กลับไปที่ด้านบนของสแต็ค

671
00:28:08,320 --> 00:28:11,350
และแล้ว pop ซึ่งหมายความว่าคุณ
ใช้ถาดบนสุดออก

672
00:28:11,350 --> 00:28:16,210
แต่สิ่งที่สำคัญเกี่ยวกับสแต็คที่
มันมีลักษณะที่อยากรู้อยากเห็นนี้

673
00:28:16,210 --> 00:28:19,560
ในฐานะที่เป็นพนักงานโรงอาหารเป็น
จัดเรียงถาดสำหรับอาหารต่อไป

674
00:28:19,560 --> 00:28:21,380
สิ่งที่เป็นไปได้
ความจริงเกี่ยวกับวิธีนักเรียน

675
00:28:21,380 --> 00:28:22,856
มีปฏิสัมพันธ์กับโครงสร้างข้อมูลนี้หรือไม่?

676
00:28:22,856 --> 00:28:24,480
ผู้ชม: พวกเขากำลังจะปรากฏหนึ่งออก

677
00:28:24,480 --> 00:28:26,550
DAVID ลัน: พวกเขากำลังจะไป
ปรากฏหนึ่งออกหวังว่าด้านบน

678
00:28:26,550 --> 00:28:28,910
มิฉะนั้นมันเป็นเพียงชนิดของโง่
ที่จะไปทุกทางไปด้านล่าง

679
00:28:28,910 --> 00:28:29,070
ใช่มั้ย?

680
00:28:29,070 --> 00:28:31,620
โครงสร้างข้อมูลไม่อนุญาตให้จริงๆ
คุณสามารถคว้าถาดด้านล่างอย่างน้อย

681
00:28:31,620 --> 00:28:32,520
อย่างง่ายดาย

682
00:28:32,520 --> 00:28:35,040
เพื่อให้มีความอยากรู้อยากเห็นนี้
สถานที่ให้บริการไปยังกอง

683
00:28:35,040 --> 00:28:39,730
ที่รายการสุดท้ายคือ
จะเป็นครั้งแรกที่ออกมาอย่างใดอย่างหนึ่ง

684
00:28:39,730 --> 00:28:43,400
และนักวิทยาศาสตร์คอมพิวเตอร์เรียก
นี้ LIFO-- สุดท้ายในครั้งแรกออกมา

685
00:28:43,400 --> 00:28:45,540
และเป็นจริงไม่ได้
โปรแกรมที่น่าสนใจ

686
00:28:45,540 --> 00:28:50,090
ก็ไม่จำเป็นต้องเป็นที่เห็นได้ชัดขณะที่บางคน
คนอื่น ๆ แต่ก็สามารถจริงจะเป็นประโยชน์

687
00:28:50,090 --> 00:28:54,040
และสามารถจริงจะดำเนินการ
ในสองวิธีที่แตกต่างกัน

688
00:28:54,040 --> 00:28:58,550
>> ดังนั้นหนึ่งและจริงให้
ไม่ให้ผมดำน้ำในที่

689
00:28:58,550 --> 00:28:59,860
ลองทำเช่นนี้แทน

690
00:28:59,860 --> 00:29:03,700
ลองดูที่หนึ่งที่เกือบจะ
ความคิดเดียวกัน แต่มันเป็นเรื่องเล็ก ๆ น้อย ๆ ที่เป็นธรรม

691
00:29:03,700 --> 00:29:04,200
ใช่มั้ย?

692
00:29:04,200 --> 00:29:07,560
หากคุณเป็นหนึ่งของเด็กผู้ชายที่แฟนเหล่านี้หรือ
สาว ๆ ที่ชอบผลิตภัณฑ์แอปเปิ้ล

693
00:29:07,560 --> 00:29:10,130
และคุณตื่นขึ้นมาที่ 03:00
เข้าแถวที่ร้านบางส่วน

694
00:29:10,130 --> 00:29:14,150
ที่จะได้รับ iPhone รุ่นใหม่ล่าสุดที่คุณ
อาจจะมีคิวขึ้นเช่นนี้

695
00:29:14,150 --> 00:29:15,800
>> ตอนนี้คิวเป็นชื่ออย่างจงใจ

696
00:29:15,800 --> 00:29:18,190
มันเป็นเส้นเพราะมี
เป็นธรรมบางส่วนไป

697
00:29:18,190 --> 00:29:18,690
ใช่มั้ย?

698
00:29:18,690 --> 00:29:21,690
มันจะดูดชนิดของถ้าคุณได้
ไปถึงที่นั่นเป็นครั้งแรกที่ Apple Store

699
00:29:21,690 --> 00:29:25,700
แต่คุณจะได้อย่างมีประสิทธิภาพล่างสุด
ถาดเพราะพนักงานแอปเปิ้ลแล้ว

700
00:29:25,700 --> 00:29:28,189
ป๊อปเป็นคนสุดท้ายที่
จริงมีอยู่ในแนวเดียวกัน

701
00:29:28,189 --> 00:29:31,230
ดังนั้นกองและคิวแม้ว่า
หน้าที่ที่พวกเขากำลังชนิดของมันเหมือนกับ

702
00:29:31,230 --> 00:29:33,105
มันเป็นเพียงแค่การเก็บสะสมนี้
ของทรัพยากรที่

703
00:29:33,105 --> 00:29:36,210
มีกำลังที่จะเติบโตและ shrink-- ที่
ด้านความเป็นธรรมนี้เพื่อมัน

704
00:29:36,210 --> 00:29:39,634
อย่างน้อยในโลกจริง
ซึ่งการดำเนินการที่คุณออกกำลังกาย

705
00:29:39,634 --> 00:29:40,800
มีความแตกต่างกันลึกซึ้ง

706
00:29:40,800 --> 00:29:43,360
stack-- คิว
rather-- กล่าวกันว่ามี

707
00:29:43,360 --> 00:29:45,320
สองการดำเนินงาน: คิว n และงคิว

708
00:29:45,320 --> 00:29:46,341

709
00:29:46,341 --> 00:29:48,090
หรือคุณสามารถเรียกพวกเขา
จำนวนของสิ่งใด ๆ

710
00:29:48,090 --> 00:29:50,770
แต่คุณก็ต้องการจับภาพ
ความคิดที่ว่าหนึ่งคือการเพิ่ม

711
00:29:50,770 --> 00:29:53,230
และหนึ่งในที่สุดการลบ

712
00:29:53,230 --> 00:29:58,840
>> ตอนนี้อยู่ใต้กระโปรงหน้ารถทั้งสองกอง
และคิวที่จะต้องดำเนินการอย่างไร

713
00:29:58,840 --> 00:30:01,390
เราจะไม่ไปลงรหัสของ
เพราะระดับที่สูงขึ้น

714
00:30:01,390 --> 00:30:03,387
ความคิดคือการจัดเรียงของที่เห็นได้ชัดมากขึ้น

715
00:30:03,387 --> 00:30:04,470
ผมหมายถึงสิ่งที่มนุษย์ทำอย่างไร

716
00:30:04,470 --> 00:30:07,030
ถ้าผมเป็นคนแรกที่แอปเปิ้ล
การจัดเก็บและนี่คือประตูหน้า

717
00:30:07,030 --> 00:30:08,130
คุณรู้ว่าฉันจะไปยืนอยู่ที่นี่

718
00:30:08,130 --> 00:30:09,750
และคนถัดไป
จะไปยืนอยู่ที่นี่

719
00:30:09,750 --> 00:30:11,500
และคนถัดไป
จะไปยืนอยู่ที่นี่

720
00:30:11,500 --> 00:30:13,792
ดังนั้นสิ่งที่โครงสร้างข้อมูล
ยืมตัวเองไปยังคิว?

721
00:30:13,792 --> 00:30:14,542
>> ผู้ชม: คิว

722
00:30:14,542 --> 00:30:15,667
DAVID ลัน: ดีคิว

723
00:30:15,667 --> 00:30:16,390
แน่ใจ

724
00:30:16,390 --> 00:30:16,920
อะไร?

725
00:30:16,920 --> 00:30:17,600
>> ผู้ชม: รายการที่เชื่อมโยง

726
00:30:17,600 --> 00:30:18,990
>> DAVID ลัน: การเชื่อมโยง
รายการที่คุณสามารถใช้

727
00:30:18,990 --> 00:30:22,500
และรายการที่เชื่อมโยงเป็นสิ่งที่ดีเพราะแล้ว
มันสามารถเติบโตได้โดยพลตราบใดที่ไม่เห็นด้วย

728
00:30:22,500 --> 00:30:24,880
จะมีบางจำนวนคงที่
ของคนที่อยู่ในร้าน

729
00:30:24,880 --> 00:30:27,030
แต่บางทีจำนวนคงที่
ในสถานที่ที่ถูกต้องตามกฎหมาย

730
00:30:27,030 --> 00:30:30,350
เพราะถ้าพวกเขาเพียง แต่มีเช่น 20
iPhones ในวันแรกอาจจะ

731
00:30:30,350 --> 00:30:33,930
พวกเขาจะต้องอาร์เรย์ของขนาด
20 เพื่อเป็นตัวแทนของคิวที่ซึ่ง

732
00:30:33,930 --> 00:30:37,070
เป็นเพียงการที่จะบอกว่าตอนนี้เมื่อเราเริ่มพูดคุย
เกี่ยวกับปัญหาเหล​​่านี้ในระดับที่สูงขึ้น

733
00:30:37,070 --> 00:30:38,890
คุณสามารถใช้มัน
ในหลายวิธีใด ๆ

734
00:30:38,890 --> 00:30:42,030
และอาจมีแค่ไป
ซื้อขายออกไปในพื้นที่และเวลา

735
00:30:42,030 --> 00:30:43,950
หรือเพียงแค่ในความซับซ้อนรหัสของคุณเอง

736
00:30:43,950 --> 00:30:45,380
>> สิ่งที่เกี่ยวกับสแต็ค?

737
00:30:45,380 --> 00:30:48,190
ดีสแต็คที่เราได้เห็นอีกด้วย
ก็อาจจะถาดเหล่านี้

738
00:30:48,190 --> 00:30:50,007
และคุณสามารถดำเนินการนี​​้อาเรย์

739
00:30:50,007 --> 00:30:53,090
แต่ในบางจุดหากคุณใช้อาร์เรย์
สิ่งที่จะเกิดขึ้นกับถาด

740
00:30:53,090 --> 00:30:54,173
คุณกำลังพยายามที่จะนำลง?

741
00:30:54,173 --> 00:30:55,170

742
00:30:55,170 --> 00:30:55,670
สิทธิ์ทั้งหมด

743
00:30:55,670 --> 00:30:57,490
คุณเท่านั้นที่จะไป
จะสามารถไปสูงมาก

744
00:30:57,490 --> 00:31:00,156
และผมคิดว่าในท้องพวกเขากำลัง
ปิดภาคเรียนจริงในการเปิดที่

745
00:31:00,156 --> 00:31:01,950
ดังนั้นแน่นอนก็เกือบ
เหมือนท้องจะใช้

746
00:31:01,950 --> 00:31:03,783
อาร์เรย์ที่มีขนาดคงที่
เพราะคุณสามารถเท่านั้น

747
00:31:03,783 --> 00:31:08,302
พอดีถาดจำนวนมากดังนั้นในการเปิดในที่
ผนังลงมาด้านล่างหัวเข่าของผู้คน

748
00:31:08,302 --> 00:31:10,010
และอื่น ๆ ที่อาจจะมี
กล่าวกันว่าเป็นอาร์เรย์

749
00:31:10,010 --> 00:31:14,300
แต่แน่นอนเราสามารถใช้ว่า
มากขึ้นโดยทั่วไปกับรายการที่เชื่อมโยง

750
00:31:14,300 --> 00:31:16,390
>> ดีสิ่งที่เกี่ยวกับการควบคุมโครงสร้างข้อมูล?

751
00:31:16,390 --> 00:31:18,760
ผมขอดึงขึ้นอีกหนึ่งภาพที่นี่

752
00:31:18,760 --> 00:31:24,710
สิ่งที่ต้องการวิธีการเกี่ยวกับที่นี่นี้หรือไม่?

753
00:31:24,710 --> 00:31:28,920
ทำไมมันอาจเป็นประโยชน์ที่จะมีไม่ได้
สิ่งที่เป็นแฟนซีเป็น Trie, ซึ่ง

754
00:31:28,920 --> 00:31:32,370
เราเห็นมีโหนดกว้างมากเหล่านี้
แต่ละที่อยู่ในอาเรย์?

755
00:31:32,370 --> 00:31:35,740
แต่ถ้าเราทำอะไรบางอย่างมากขึ้น
ก็เหมือนต้นไม้ครอบครัวโรงเรียนเก่า

756
00:31:35,740 --> 00:31:38,110
แต่ละโหนดมีที่นี่
เป็นเพียงการจัดเก็บจำนวนมาก

757
00:31:38,110 --> 00:31:42,180
แทนชื่อหรือลูกหลาน
เป็นเพียงการจัดเก็บตัวเลขเช่นนี้

758
00:31:42,180 --> 00:31:45,250
>> ดีศัพท์แสงที่เราใช้ใน
โครงสร้างข้อมูลที่ถูกพยายามทั้งสอง

759
00:31:45,250 --> 00:31:49,510
และต้นไม้ที่ Trie อีกครั้งเป็น
เพียงหนึ่งที่มีโหนดมีอาร์เรย์

760
00:31:49,510 --> 00:31:51,680
ก็ยังคงเป็นสิ่งที่คุณอาจจะ
ใช้จากโรงเรียนชั้นประถมศึกษาปี

761
00:31:51,680 --> 00:31:53,860
เมื่อคุณทำในครอบครัว
ใบและราก tree--

762
00:31:53,860 --> 00:31:57,250
ของต้นไม้และเด็กของ
พ่อแม่และพี่น้องของมัน

763
00:31:57,250 --> 00:32:03,670
และเราอาจจะใช้ต้นไม้
เช่นเป็นเพียงเช่นนี้

764
00:32:03,670 --> 00:32:07,420
ต้นไม้ถ้ามันเป็นโหนดหนึ่ง
วงการเหล่านี้ที่มีตัวเลข

765
00:32:07,420 --> 00:32:09,947
ก็จะไม่ให้มีการ
หนึ่งในตัวชี้ แต่ทั้งสอง

766
00:32:09,947 --> 00:32:11,780
และทันทีที่คุณเพิ่ม
ตัวชี้ที่สองคุณ

767
00:32:11,780 --> 00:32:13,905
จริงสามารถทำให้การจัดเรียง
ของข้อมูลสองมิติ

768
00:32:13,905 --> 00:32:14,780
โครงสร้างในหน่วยความจำ

769
00:32:14,780 --> 00:32:16,660
เหมือนสองมิติ
อาร์เรย์ที่คุณสามารถ

770
00:32:16,660 --> 00:32:18,904
มีชนิดของสองมิติ
รายการเชื่อมโยง แต่คน

771
00:32:18,904 --> 00:32:20,820
ที่เป็นไปตามรูปแบบ
ที่ไม่มีรอบ

772
00:32:20,820 --> 00:32:24,487
มันอย่างแท้จริงต้นไม้ที่มีอย่างใดอย่างหนึ่ง
วิธีที่ปู่ย่าตายายที่นี่แล้ว

773
00:32:24,487 --> 00:32:27,320
ผู้ปกครองบางคนและเด็กและ
หลานและเหลน

774
00:32:27,320 --> 00:32:28,370
เป็นต้น

775
00:32:28,370 --> 00:32:32,390
>> แต่สิ่งที่เป็นจริงเกี่ยวกับเรื่องนี้เรียบร้อยเกินไป
เพียงเพื่อหยอกล้อคุณมีบิตของรหัส

776
00:32:32,390 --> 00:32:35,370
การเรียกคืนจากการเรียกซ้ำ
เดี๋ยวกลับโดย

777
00:32:35,370 --> 00:32:38,220
คุณเขียนฟังก์ชันที่เรียกตัวเองว่า

778
00:32:38,220 --> 00:32:41,140
นี่เป็นโอกาสที่สวยงาม
ในการดำเนินการบางสิ่งบางอย่าง

779
00:32:41,140 --> 00:32:42,920
เช่นการเรียกซ้ำเพราะพิจารณานี้

780
00:32:42,920 --> 00:32:43,860
>> นี้เป็นต้นไม้

781
00:32:43,860 --> 00:32:48,040
และฉันได้รับทางทวารหนั​​กเล็ก ๆ น้อย ๆ กับวิธีการ
ฉันใส่จำนวนเต็มไปที่ถนน

782
00:32:48,040 --> 00:32:51,020
มากเสียจนมันมีพิเศษ
name-- ค้นหาต้นไม้ไบนารี

783
00:32:51,020 --> 00:32:53,460
ตอนนี้เราเคยได้ยินไบนารี
ค้นหา แต่คุณสามารถ

784
00:32:53,460 --> 00:32:55,180
ทำงานหลังจากชื่อสิ่งนี้?

785
00:32:55,180 --> 00:32:59,280
เป็นรูปแบบของวิธีการที่ฉันคืออะไร
แทรกจำนวนเต็มเป็นต้นไม้นี้หรือไม่?

786
00:32:59,280 --> 00:33:00,696
มันไม่โดยพลการ

787
00:33:00,696 --> 00:33:01,570
มีรูปแบบบางส่วนเป็น

788
00:33:01,570 --> 00:33:02,090
ใช่

789
00:33:02,090 --> 00:33:03,370
>> ผู้ชม: คนเล็กทางด้านซ้าย

790
00:33:03,370 --> 00:33:03,690
>> DAVID ลัน: ใช่

791
00:33:03,690 --> 00:33:05,062
คนเล็กจะอยู่ทางซ้ายมือ

792
00:33:05,062 --> 00:33:06,270
คนที่ใหญ่กว่าอยู่ทางขวา

793
00:33:06,270 --> 00:33:12,940
ดังกล่าวว่าเป็นคำสั่งที่แท้จริงคือ
พ่อแม่มากกว่าเด็กทางด้านซ้ายของ

794
00:33:12,940 --> 00:33:14,850
แต่น้อยกว่าเด็กขวา

795
00:33:14,850 --> 00:33:17,750
และที่อยู่คนเดียวคือแม้
ความหมายของคำพูดซ้ำ

796
00:33:17,750 --> 00:33:20,500
เพราะคุณสามารถนำมาใช้ว่า
ตรรกะเดียวกันทุกโหนด

797
00:33:20,500 --> 00:33:23,080
และมันก้น
จากกรณีฐานถ้าคุณ

798
00:33:23,080 --> 00:33:25,740
จะเมื่อคุณตีหนึ่งของ
ใบเพื่อที่จะพูด

799
00:33:25,740 --> 00:33:28,580
ที่ปล่อยให้มีเด็กต่อไป

800
00:33:28,580 --> 00:33:30,614
>> ตอนนี้วิธีที่คุณอาจพบว่าจำนวน 44?

801
00:33:30,614 --> 00:33:32,280
คุณจะเริ่มต้นที่รากและพูดว่า HM

802
00:33:32,280 --> 00:33:35,690
55 ไม่ได้ 44 ดังนั้นฉันต้องการที่จะไป
ขวาหรือฉันต้องการที่จะไปทางซ้าย?

803
00:33:35,690 --> 00:33:37,190
ดีอย่างเห็นได้ชัดคุณต้องการไปทางด้านซ้าย

804
00:33:37,190 --> 00:33:40,060
และก็เช่นเดียวกับโทรศัพท์มือถือ
ตัวอย่างเช่นในการค้นหาหนังสือไบนารี

805
00:33:40,060 --> 00:33:41,099
มากขึ้นโดยทั่วไป

806
00:33:41,099 --> 00:33:43,390
แต่เรากำลังดำเนินการนั้น
ตอนนี้เล็ก ๆ น้อย ๆ แบบไดนามิก

807
00:33:43,390 --> 00:33:45,339
กว่าอาร์เรย์อาจอนุญาตให้

808
00:33:45,339 --> 00:33:48,130
และในความเป็นจริงถ้าคุณต้องการดู
รหัสที่ได้อย่างรวดเร็วก่อนว่า

809
00:33:48,130 --> 00:33:49,671
ดูเหมือนว่าทั้งกลุ่มของเส้น

810
00:33:49,671 --> 00:33:51,220
แต่มันง่ายอย่างสวยงาม

811
00:33:51,220 --> 00:33:54,490
ถ้าคุณต้องการที่จะใช้ฟังก์ชั่น
ที่เรียกว่าการค้นหาที่มีจุดมุ่งหมายในชีวิต

812
00:33:54,490 --> 00:33:57,290
คือการค้นหาค่า
เช่น n, จำนวนเต็ม

813
00:33:57,290 --> 00:34:01,756
และคุณผ่านในหนึ่ง pointer--
ตัวชี้ไปยังโหนดราก,

814
00:34:01,756 --> 00:34:04,380
ค่อนข้างของต้นไม้ที่จากการที่
คุณสามารถเข้าถึงได้ทุกอย่างอื่น

815
00:34:04,380 --> 00:34:08,850
แจ้งให้ทราบว่าตรงไปตรงมา
คุณสามารถใช้ตรรกะ

816
00:34:08,850 --> 00:34:10,880
ถ้าต้นไม้เป็น null
เห็นได้ชัดว่ายังไม่ได้มี

817
00:34:10,880 --> 00:34:11,880
ขอเพียงกลับเท็จ

818
00:34:11,880 --> 00:34:12,000
ใช่มั้ย?

819
00:34:12,000 --> 00:34:14,040
ถ้าคุณส่งมันไม่มีอะไร
ไม่มีอะไรที่นั่น

820
00:34:14,040 --> 00:34:17,900
>> มิฉะนั้นถ้า n มีค่าน้อยกว่า
ลูกศรต้นไม้ n-- ตอน arrow n,

821
00:34:17,900 --> 00:34:20,670
จำเราได้นำเสนอซุปเปอร์
ในเวลาสั้น ๆ ในวันอื่น ๆ

822
00:34:20,670 --> 00:34:25,100
และนั่นก็หมายความว่าเดอ้างอิง
ตัวชี้และดูที่เขตข้อมูลที่เรียกว่า n

823
00:34:25,100 --> 00:34:27,690
ดังนั้นจึงหมายความว่าไปที่นั่นและ
ดูข้อมูลที่เรียกว่า n

824
00:34:27,690 --> 00:34:33,810
ดังนั้นถ้า n ค่าคุณได้รับจะน้อย
กว่ามูลค่าในจำนวนเต็มต้นไม้

825
00:34:33,810 --> 00:34:35,449
ที่คุณต้องการที่จะไป?

826
00:34:35,449 --> 00:34:36,389
ไปทางซ้าย

827
00:34:36,389 --> 00:34:37,780
>> เพื่อแจ้งให้ทราบล่วงหน้าเรียกซ้ำ

828
00:34:37,780 --> 00:34:39,860
ฉัน returning-- ไม่เป็นความจริง

829
00:34:39,860 --> 00:34:40,989
ไม่เท็จ

830
00:34:40,989 --> 00:34:45,670
ฉันกลับมาสิ่งที่คำตอบ
เป็นจากการเรียกตัวเองผ่าน

831
00:34:45,670 --> 00:34:50,100
n อีกครั้งซึ่งเป็นซ้ำซ้อน
แต่เป็นสิ่งที่แตกต่างกันเล็กน้อยในตอนนี้?

832
00:34:50,100 --> 00:34:51,989
ฉันทำให้ปัญหาวิธีเล็ก?

833
00:34:51,989 --> 00:34:54,920
ฉันผ่านในขณะที่สอง
อาร์กิวเมนต์ไม่ใช่รากของต้นไม้

834
00:34:54,920 --> 00:34:59,616
แต่เด็กซ้ายในกรณีนี้

835
00:34:59,616 --> 00:35:00,990
ดังนั้นฉันผ่านในเด็กซ้าย

836
00:35:00,990 --> 00:35:04,720
>> ในขณะเดียวกันถ้า n มีขนาดใหญ่กว่า
โหนดฉันกำลังมองหาที่

837
00:35:04,720 --> 00:35:06,690
ฉันค้นหาด้านขวามือ

838
00:35:06,690 --> 00:35:10,880
มิฉะนั้นถ้าต้นไม้ไม่เป็นโมฆะและ
ถ้าองค์ประกอบไม่ไปทางซ้าย

839
00:35:10,880 --> 00:35:13,240
และก็ไม่ไปทางขวา
สิ่งที่น่าพิศวงกรณี?

840
00:35:13,240 --> 00:35:14,630

841
00:35:14,630 --> 00:35:18,440
เราได้พบจริงโหนดใน
คำถามและเพื่อให้เรากลับจริง

842
00:35:18,440 --> 00:35:21,490
>> ดังนั้นเราจึงได้เพียงแค่รอยขีดข่วนบนพื้นผิว
ตอนนี้บางส่วนของโครงสร้างข้อมูลเหล่านี้

843
00:35:21,490 --> 00:35:24,370
ในปัญหาการตั้งห้าคุณจะ
สำรวจเหล่านี้ยังเพิ่มเติม

844
00:35:24,370 --> 00:35:27,250
และคุณจะได้รับการออกแบบของคุณ
ทางเลือกของวิธีการไปเกี่ยวกับเรื่องนี้

845
00:35:27,250 --> 00:35:30,250
สิ่งที่ผมอยากจะสรุปได้ใน
เป็นเพียง 30 ทีเซอร์ที่สอง

846
00:35:30,250 --> 00:35:32,080
ของสิ่งที่รอคอยในสัปดาห์หน้าและอื่น ๆ

847
00:35:32,080 --> 00:35:35,390
>> ในขณะที่เรา begin-- ขอบคุณคุณอาจ
think-- การเปลี่ยนแปลงของเราอย่างช้าๆ

848
00:35:35,390 --> 00:35:38,680
จากโลกของ C และล่าง
รายละเอียดการปฏิบัติระดับ

849
00:35:38,680 --> 00:35:42,090
กับโลกที่เราสามารถใช้สำหรับ
รับว่าคนอื่นมีในที่สุด

850
00:35:42,090 --> 00:35:44,010
ใช้ข้อมูลเหล่านี้
โครงสร้างสำหรับเรา

851
00:35:44,010 --> 00:35:47,570
และเราจะเริ่มต้นที่จะเข้าใจ
โลกแห่งความจริงหมายความว่าในการดำเนินการ

852
00:35:47,570 --> 00:35:50,560
โปรแกรมบนเว็บและ
เว็บไซต์มากขึ้นโดยทั่วไป

853
00:35:50,560 --> 00:35:52,910
และนอกจากนี้ยังมีการรักษาความปลอดภัยมาก
ผลกระทบที่เราได้เท่านั้น

854
00:35:52,910 --> 00:35:54,850
เริ่มที่จะมีรอยขีดข่วนพื้นผิวของ

855
00:35:54,850 --> 00:35:57,320
นี่คือสิ่งที่รอเรา
ต่อนี้ไป

856
00:35:57,320 --> 00:36:00,480
>> [การเล่นวิดีโอ]

857
00:36:00,480 --> 00:36:03,432

858
00:36:03,432 --> 00:36:12,780
>> พระองค์จึงมาพร้อมกับข้อความ
กับโปรโตคอลทั้งหมดของเขาเอง

859
00:36:12,780 --> 00:36:26,110

860
00:36:26,110 --> 00:36:30,894
เขามาถึงโลกของโหดร้าย
ไฟร์วอลล์เราเตอร์ไม่สนใจ,

861
00:36:30,894 --> 00:36:33,368
และอันตรายที่ไกลยิ่งกว่าความตาย

862
00:36:33,368 --> 00:36:35,280

863
00:36:35,280 --> 00:36:36,236
เขาเป็นอย่างรวดเร็ว

864
00:36:36,236 --> 00:36:37,980
เขาเป็นคนที่แข็งแกร่ง

865
00:36:37,980 --> 00:36:42,830
เขาเป็น TCP / IP และเขาก็มีที่อยู่ของคุณ

866
00:36:42,830 --> 00:36:45,290

867
00:36:45,290 --> 00:36:48,074
"นักรบแห่งสุทธิ."

868
00:36:48,074 --> 00:36:49,660
[จบการเล่นวิดีโอ]

869
00:36:49,660 --> 00:36:50,910
DAVID ลัน: มาในสัปดาห์หน้า

870
00:36:50,910 --> 00:36:51,880
เราจะเห็นคุณแล้ว

871
00:36:51,880 --> 00:36:54,615

872
00:36:54,615 --> 00:36:56,060
[การเล่นวิดีโอ]

873
00:36:56,060 --> 00:36:59,240
ในอนาคตและตอนนี้ "คิดลึก"
โดย Daven อัม

874
00:36:59,240 --> 00:37:02,030

875
00:37:02,030 --> 00:37:05,820
เดวิดเสมอเริ่มต้น
บรรยายกับ "สิทธิทั้งหมด."

876
00:37:05,820 --> 00:37:08,750
ทำไมไม่ "นี่คือการแก้ปัญหา
เพื่อแก้ไขปัญหาในสัปดาห์นี้ชุด "

877
00:37:08,750 --> 00:37:12,180
หรือ "เรากำลังให้ทุกท่าน"

878
00:37:12,180 --> 00:37:13,380
[หัวเราะ]

879
00:37:13,380 --> 00:37:15,530
[จบการเล่นวิดีโอ]