프로젝트에서 일반적으로 사용되는 Linux 명령으로 인해 발생하는 고전적인 알고리즘 질문

　　小时候家里定了《读者》的月刊，里面记录一个故事：说有有个偏僻的乡村一日突然来了一个美女，她携着万贯家财子女在当地安家落户，成了当地的乡绅。她让她的子女世世代代的保守这个秘密，直到这个秘密不会再对家族带来灾难。她就是陈圆圆。当年吴三桂领清兵入关，冲冠一怒为红颜，改写了中国的历史，自己却能全身而退的那个人。

　　周五例行公事的查看一下离线数据推送项目的数据和log。将log用awk分段之后，我想知道实时数据前10个被重复发送的数据ID都被重复发送了几次，从而找到进一步优化的入手点，天知道我对这个项目已经进行了多少次优化了。于是linux命令就是

 cat transmission.log |grep 'IncrementAlbumService.java:146'|awk '{print $6}'|awk -F ',' '{print $1}'| sort |uniq -c| sort -nr |head

　결과가 너무 죄책감이 들었습니다

(데이터 보안, 우리 프로젝트의 ID 규칙 부분은 표시되지 않습니다)

그들의 운영과 관련이 있지만 데이터 변경 사항을 감지하여 보냈어야 했는데, 하지만 그만큼 높은 재발행률을 자랑합니다. 업데이트 서비스의 인터페이스나 오프라인 서비스의 인터페이스에 관계없이 여전히 최적화할 수 있는 지점이 있습니다. 얘들아, 저 남자 아이돌들이 등장할 때 드라이어나 인공 물뿌리개로 그림을 그리는 것과 내 생각은 늘 달랐다. 이 결과 외에도 나는 또 다른 고전적인 알고리즘 문제에 대해서도 생각하고 있습니다. 약 10,000줄로 구성된 텍스트 파일이 있고 각 줄에 한 단어가 있으며 가장 자주 발생하는 상위 10개 단어를 계산해야 합니다.

　이 알고리즘 문제의 경우 위의 Linux 명령은 sort|uniq -c |sort -nr | 시간 복잡도는 다음 중 가장 큽니다.

　1> 먼저 정렬을 수행합니다.

　 직접 삽입 정렬: 순서가 지정된 목록에 요소를 계속 삽입합니다. 가장 나쁜 시간 복잡도는 O(n² )

　입니다. 감소된 증분을 갖는 삽입 정렬, 불안정, 증분 인수 수열의 선택에 따라 최악의 시간 복잡도는 O(n²)

　 단순 선택 정렬: 정렬할 숫자 중에서 가장 작은 숫자 또는 가장 큰 숫자를 선택하여 교환 정렬되지 않은 첫 번째 위치의 최악의 시간 복잡도는 O(n²)

　　이진 선택 정렬: 각 단순 선택 정렬은 두 가지 요소를 결정하므로 주기가 절반으로 줄어들 수 있습니다.

　 힙 정렬: 트리 선택 정렬, 큰 루트 힙, 작은 루트 힙. 최악의 시간 복잡도는 O(N*logN)

　버블 정렬: 인접한 두 숫자를 비교하고 교환할 때마다 최악의 시간 복잡도는 O(n²)

　퀵 정렬: 선택 벤치마크 요소, 매번 정렬할 요소를 분할할 때 최악의 시간 복잡도는 O(n²)

　 병합 정렬: 두 개의 정렬된 목록을 새로운 정렬된 목록으로 결합합니다. 최악의 시간 복잡도는 O(N*logN)

　버킷 정렬: 공간을 시간으로 교환하는 알고리즘, 복잡도는 O(n)

　　Radix 정렬: 수십만 자리에 따라 할당하고 수집하며, 시간 복잡도는 O(dn)

2> is O(n)

　 3> 정렬의 시간 서비스 정도는 1>

　 4> 정렬 후의 시간 복잡도는 O(1)

사용된 알고리즘도 파일 크기와 관련이 있습니다. , 파일이 너무 크고 데이터가 너무 많으면 파일을 분할하고 별도로 정렬한 다음 여러 방법으로 병합해야 합니다. 그래서 여기서는 단어의 수가 언급됩니다.

　 Linux 명령이 없는 경우 고전적인 해결책은 먼저 사전 트리를 사용하여 단어 빈도를 계산한 다음 큰 루트 힙을 사용하는 것입니다. 먼저 타이어 트리라고도 불리는 딕셔너리 트리를 소개하겠습니다. 검색 엔진은 이것을 텍스트 단어 빈도 통계를 만들기 위해 자주 사용하고 단어 분할 알고리즘도 이것을 기본 데이터 구조로 사용하기 때문에 이에 대해 조금 알고 있습니다. 장점은 불필요한 문자열 비교를 최소화하고 쿼리 효율성이 해시 테이블보다 높다는 것입니다. 핵심 아이디어는 공간을 시간으로 교환하고 공개 접두사를 사용하여 쿼리 시간 오버헤드를 줄이는 것입니다. 그래서 통계라고 하면 가장 먼저 떠오르는 것이 딕셔너리 트리이다. 단어 빈도를 계산할 때 최대 10개의 단어 빈도 배열을 유지하면 루프 처리에서 비교할 때 시간 복잡도가 10배 더 높아집니다. 따라서 먼저 통계를 만든 후 시간 효율성 측면에서 상위 10위를 선정하는 것이 더 적절하다.

사실 저는 알고리즘에 대해 잘 모르고 사용법만 알고 있어요. 내 전 동료가 내가 WeChat에 쓴 기사를 읽고 나에게 물었습니다: "피드 스트리밍이 매우 기술적인 작업입니까?" 그의 질문은 나에게 키가 크고 부자이며 잘생긴 척을 고집했던 "Sword of Immortals"의 Li Xiaoyao를 생각나게 했습니다. 식당에서 그가 가장 비싼 요리를 주문하고 싶다고 말했을 때, Ling'er는 Li Xiaoyao에게 "샤오야오 형제님, 야채를 곁들인 쇠고기 튀김이 아주 비싼 요리인가요?"라고 물었습니다. 동료가 JD.com에 있어서 제 의견을 진지하게 물어보고 모모로 갈까 고민 중이었지만 저는 마치 세상을 본 적이 없는 리샤오야오처럼 느껴졌습니다. 피드 흐름의 비즈니스 로직은 기술적인 내용이 있는지 여부에 따라 어떤 방식으로든 수행될 수 있습니다. 피드 스트림을 조립하는 방법을 소개하기 위해 특허를 작성했습니다. 프로세스가 완료되지 않았으므로 그때까지 계산 방법을 공개하지 않겠습니다. 하지만 열심히 생각해보면 아직 최적화 포인트가 많이 남아있습니다. 재작년 모먼츠 게임을 좋아했을 때, 내가 삭제한 모멘트가 다시 나타나거나, 나 자신이나 다른 사람의 모멘트에 있던 최근 데이터가 갑자기 모두 사라지고, 아주 오래된 데이터(예: 두 달 전)만 남는 경우가 종종 있었습니다. . 1년 전의 데이터는 하루 후에 자동으로 복원됩니다. 그것은 모두 전략의 문제입니다. WeChat Moments에는 많은 문제가 있습니다. 우리 제품 중 하나인 mm는 위챗 아키텍트의 가족이기 때문에 크게 불평하지는 않겠습니다.

오늘은 일요일이지만 상상력을 조금 발휘해도 되지만 테마가 있어야 합니다. 이전 예에는 고전적인 상위 K 문제가 있습니다. 검색 엔진은 가장 인기 있는 쿼리 문자열을 계산해야 하는 경우가 많기 때문에 상위 K 질문이 기본입니다. TopK 문제는 작은 루트 힙을 사용합니다. K 크기의 작은 루트 힙을 유지하고 비교할 요소를 순회하며 각각 다음 요소와 비교합니다. 루트 요소보다 작으면 반드시 상위 K에 들어가지 않고 제거된다는 의미입니다. 루트 요소보다 크면 루트 요소를 제거합니다. 그런 다음 트리를 최소 힙으로 조정하고 비교를 계속합니다.

　최소 힙은 완전한 이진 트리이며, 리프가 아닌 각 노드의 값은 해당 하위 노드의 값보다 크지 않습니다. 이 규칙이 깨지면 리프가 아닌 첫 번째 노드부터 루트 노드까지 상향식 순서로 조정이 이루어져야 합니다.

다음주에 Hulu에서 인터뷰하기로 했는데 아직 안 했으니 아마 안 할 것 같아요. 2년 전, 전 동료가 아마존을 추천했지만, 당시에는 채용 중이 아니었던 것 같아 면접을 보러 가라는 요청을 받지 않았습니다. 외국 회사 면접을 이런 식으로 가본 적이 없어서 루틴이 어떤지는 잘 모르겠습니다. 지금부터 준비하면 아마도 국경절 이후에는 합격할 수 있을 것 같습니다. 면접에 혼자 가면 많이 불리할 것 같아요. 전혀 나쁘지 않을 것입니다. 매우 불안정할 것입니다. 내 글을 읽은 친구들은 내 글이 매우 난잡하고 복잡하다고 생각할 수도 있다. 이것은 실제로 내 인생의 경우입니다. 나는 폭넓은 지식을 갖고 있고, 매우 변덕스럽고 거리낌이 없습니다. 이는 한편으로는 창의성의 기초가 되지만, 다른 한편으로는 자신을 표현하는 능력에 도움이 되지 않습니다. 점. 뇌는 컴퓨터와 같습니다. 병렬 프로그램이 많고 메모리가 충분하지 않으며 데이터가 많습니다. 메모리 페이징으로 인해 지속적인 디스크 스와핑이 발생합니다. 인터뷰와 같이 시간에 민감한 작업은 쉽게 시간 초과 반환으로 이어질 수 있습니다. 나는 기술발명 특허를 너무 많이 갖고 있는데 지금은 내가 무엇을 발명했는지조차 기억나지 않는 것 같다. 그냥 버스를 탔어요. 사람이 거의 없어서 어디서 내릴지 물어보더군요. 사람이 내리지 않는 곳에 정차한다는 뜻이었습니다. 기억하는 데 오랜 시간이 걸렸습니다. 내 두뇌는 비동기식 비차단 모드에서 더 많이 작동합니다. 실제로 인터뷰와 같은 작업에는 동기식 차단이 더 좋습니다. 그러나 모든 것에는 해결책이 있습니다. 해결책을 찾을 수 없다면 단지 능력이 부족할 뿐입니다. 단, 면접은 팀워크, 대화능력 등 종합적인 능력을 검토하는 것입니다. 나는 우리 부서의 어느 누구도 "샤오징은 매우 똑똑하다"는 말에 이의를 제기하지 않을 것이라고 믿습니다. 또한, 부서나 직장에서 함께 협업하는 동료들은 나를 소통하기 어려운 사람, 어울리기 어려운 사람으로 생각하지 않을 것이라고 믿습니다. 그런데 저는 인터뷰할 때 말하는 방법을 잊어버리는 편이에요. 하지만 이 문제 때문에 면접에 실패하더라도 불만은 없습니다. 면접관은 미래의 동료이자 리더이기 때문에 면접관과 호흡이 맞지 않으면 앞으로 자신의 능력을 발휘하지 못할 수도 있습니다. 만약 당신이 면접에서 좋은 성적을 내지 못하더라도 여전히 자신의 능력이 충분하다고 느낀다면, 당신의 수준이 충분히 높지 않고 정말 뛰어난 사람들이 어떤 모습인지 본 적이 없을 가능성이 높습니다. 하지만 나는 벽에 부딪힐 때에도 계속해서 일을 하는 사람이다. 내가 뭔가를 포기하기로 결정했다면 그것은 할 가치가 없기 때문이다.

　 저는 일하는 것을 좋아하고, 60세가 되어도 창의적인 직업을 갖는 것이 목표입니다. 그래서 국내 인터넷 회사들이 40세에 은퇴를 허락해 줄까 두렵습니다. 한 가지 더 중요한 것은 나만의 검색 엔진 미들웨어를 만들고 싶다는 것인데, 국내 인터넷 회사들은 주로 사용자 중심으로 되어 있기 때문에 이를 할 수 있는 에너지를 갖기가 어려울 것 같습니다. 물론, Hulu에 갈 수 없다면 검색 엔진이 계속 해야 합니다. 단지 시간을 어떻게 배분하느냐의 문제일 뿐입니다.

사실 저는 벽에 부딪히는 걸 좋아하는데, 어쩌면 너무 빨리 어른이 되고 싶지 않아서일 수도 있어요. 매일매일 성숙하고 우아한 행동을 한다면, 자신이 잘 못하는 것, 잘못될 수 있는 것을 숨겨야 합니다. 결과적으로 나는 매일매일 행복하겠지만 평생 이대로 있을 수도 있다. 원래는 플레이보이였으나 집안이 쇠퇴하면서 위대한 인물이 된 인물들이 역사적으로 많이 있습니다. 책에는 인생의 두 가지 전환점이 있는데, 고귀한 사람을 만나는 것과 좌절을 만나는 것이다. 젊고 마음이 열려 있으면 고귀한 사람을 만나 마음을 열면 깨달음을 얻을 수 있습니다. 경험이 늘어남에 따라 사람들은 주변 정보를 더 선별적으로 받아들일 것입니다. 이때 인생을 다시 생각하기 전에 큰 좌절을 겪어야 할 수도 있습니다. 더 나은 미래를 볼 수 있다면 기꺼이 혼자 가서 배를 불태울 의향이 있습니다. 하루살이보다는 우여곡절을 겪는게 낫다. 살고 싶다면 멋진 삶을 살아라~~

위 내용은 프로젝트에서 일반적으로 사용되는 Linux 명령으로 인해 발생하는 고전적인 알고리즘 질문의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!