精华内容
下载资源
问答
  • MySQL源码分析之use database_name切换表空间切换表空间源码分析客户端流程服务端流程 说明: 以下所有说明都以 MySQL 5.7.25 源码为例 ,存储引擎为InnoDB。 切换表空间 mysql客户端登录之后,需要使用use ...

    说明:
    以下所有说明都以 MySQL 5.7.25 源码为例 ,存储引擎为InnoDB。

    切换表空间

    mysql客户端登录之后,需要使用use database_name选取表空间并切换到具体的表空间下进行操作,否则会报错:
    使用前未使用use database_name

    mysql>show tables;
    ERROR 1046 (3D000): No database selected
    

    选取并切换:

    mysql>use test;
    mysql>show tables;
    +-----------------+
    | Tables_in_test  |
    +-----------------+
    | t1              |
    | t2              |
    +-----------------+
    2 rows in set (0.00 sec)
    

    切换表空间源码分析

    客户端流程

    在mysql客户端上执行use database_name,其实背后是一套组合的操作命令,大概的主要操作流程为;

    • 通过SELECT DATABASE()获取当前的database的名称;
    • 比较use database_name中的namecurrent_db_name是否一致;
    • 不一致则通过show databases查询所有的databases并且校验选择use database_name中对应的database;
    • 通过show tables打开所有的tables;
    mysql_client
    com_use(String *buffer MY_ATTRIBUTE((unused)), char *line)
      get_current_db();
      >get_current_db
        if !mysql_query(&mysql, "SELECT DATABASE()") && res=mysql_use_result(&mysql)
          MYSQL_ROW = mysql_fetch_row(res)
          if row && row[0]
            current_db = my_strdup(PSI_NOT_INSTRUMENTED, row[0], MYF(MY_WME))
            mysql_free_result(res)
          fi
        fi
      <get_current_db
      if !current_db || cmp_database(charset_info, current_db, tmp) //current_db="innodb", tmp="ywx"
      fi
      
      if select_db; THEN//select_db = 2
        if mysql_select_db(&mysql, tmp)
        fi
        my_free(current_db)
        current_db = my_strdup(PSI_NOT_INSTRUMENTED, tmp, MYF(MY_WME)
      fi
      if (select_db > 1)
          build_completion_hash(opt_rehash, 1)
          >build_completion_hash
            if (mysql_query(&mysql,"show databases") == 0)// "show databasess"
            fi
            if (mysql_query(&mysql,"show tables")==0)//"show tables"
              if !(tables = mysql_store_result(&mysql))
              else
                while table_row=mysql_fetch_row(tables)
                do
                done             
              fi
            fi
          <build_completion_hash
      fi
    

    服务端流程

    服务端对应客户端不同阶段的请求处理为:

    • 处理SELECT DATABASE()请求;
      SELECT DATABASE()走的是SELECT流程,DATABASE()作为一个function的形式进行处理,其yacc语法规则为:
    function_call_conflict:
    	ASCII_SYM '(' expr ')'
    	{
    	  $$= NEW_PTN Item_func_ascii(@$, $3);
    	}
    	...
    	| DATABASE '(' ')'
    	{
    	  $$= NEW_PTN Item_func_database(@$);
    	}
    
    • 处理show databases请求, yacc语法规则为:
    show:
      SHOW
      {
        LEX *lex=Lex;
        new (&lex->create_info) HA_CREATE_INFO;
      }
      show_param
      ;
    show_param:
      DATABASES opt_wild_or_where
      {
         LEX *lex= Lex;
         lex->sql_command= SQLCOM_SHOW_DATABASES;
         if (prepare_schema_table(YYTHD, lex, 0, SCH_SCHEMATA))
           MYSQL_YYABORT;
      }
    
    • 处理show tablesyacc语法规则为:
    show:
      SHOW
      {
        LEX *lex=Lex;
        new (&lex->create_info) HA_CREATE_INFO;
      }
      show_param
      ;
    show_param:
     | opt_full TABLES opt_db opt_wild_or_where
       {
         LEX *lex= Lex;
         lex->sql_command= SQLCOM_SHOW_TABLES;
         lex->select_lex->db= $3;
         if (prepare_schema_table(YYTHD, lex, 0, SCH_TABLE_NAMES))
           MYSQL_YYABORT;
       }
    
    mysql_execute_command
      switch lex->sql_command:
      case SQLCOM_SHOW_DATABASES:
      case SQLCOM_SHOW_TABLES:
      case SQLCOM_SELECT:
        res= execute_sqlcom_select(thd, all_tables)
        >execute_sqlcom_select
          if !open_tables_for_query(thd, all_tables, 0); THEN
            if lex->is_explain(); THEN
              Query_result *const result= new Query_result_send
              res= handle_query(thd, lex, result, 0, 0)
            else
              res= handle_query(thd, lex, result, 0, 0)
            fi
          fi
        <execute_sqlcom_select
    
    handle_query
      const bool single_query= unit->is_simple()
      //phase 1: prepare
      if single_query; THEN
        unit->set_limit(unit->global_parameters())
        select->context.resolve_in_select_list= true
        select->set_query_result(result)
        select->make_active_options(added_options, removed_options)
        select->fields_list= select->item_list
        if select->prepare(thd); THEN
        fi
        unit->set_prepared()
      ELSE
        if unit->prepare(thd, result, SELECT_NO_UNLOCK | added_options, removed_options); THEN
        fi
      fi
      if lock_tables(thd, lex->query_tables, lex->table_count, 0); THEN
      fi
      //register query result in cache
      query_cache.store_query(thd, lex->query_tables)
      
      //phase 2: optimize
      if single_query; THEN
        if select->optimize(thd); THEN
        fi
        unit->set_optimized()
      ELSE
        if select->optimize(thd); THEN
        fi
      fi
      
      //phase 3: execute
      if lex->is_explain(); THEN
        if explain_query(thd, unit); THEN
        fi
      ELSE
        if single_query; THEN
          select->join->exec()
          unit->set_executed()
          if thd->is_error() ; THEN
            goto err;
        else
          if (unit->execute(thd)); THEN
            goto err;
      fi
      res= unit->cleanup(false)
    
    展开全文
  • 数据库查询代价估算优化深度介绍,帮助大家详细了解代价估算,帮助开发写出更高效的SQL。

    数据库查询代价估算优化的深度介绍

    今天在看一本书的时候发现在查询代价估算一节讲的不是很清晰,受篇幅限制吧。例如原文会出现这样两句话“索引列出现在JOIN/ON子句中,作为连接条件,不可使用索引”,“索引列出现在JOIN/ON子句中,作为限制条件满足”key<op>常量”格式可用索引”,这样的话就很容易误导读者,没有将本质叙述出来。真实原因,如果驱动表行数很少,在约束条件上内表走索引过滤性强的时候,那么通常选择走索引代价会更小。举个例子:

    test=# create table t(c1 int unique, c2 int unique);
    
    test=# create table t1(c1 int primary key, c2 int, c3 int, c4 int 
    unique);
    
    test=# explain select * from t join t1 on t.c2 = t1.c4 where t.c1 = 1;
    
    +---------------------------------------------------------------------------+
    | QUERY PLAN|
    +---------------------------------------------------------------------------+
    | Nested Loop  (cost=0.31..16.36 rows=1 width=24)   |
    |   ->  Index Scan using t_c1_key on t  (cost=0.16..8.17 rows=1 width=8)|
    | Index Cond: (c1 = 1)  |
    |   ->  Index Scan using t1_c4_key on t1  (cost=0.15..8.17 rows=1 width=16) |
    | Index Cond: (c4 = t.c2)   |
    +---------------------------------------------------------------------------+
    5 rows in set
    

    在t1索引列c4上,并没有常量condition,也没有其等值的t.c2的常量condition。但t.c1 = 1这个equal condition可以估算返回1行数据,获得这一行数据后t.c2为常量值,那么可以利用t1.c4 = t.c2这一条件走索引t1_c4_key快速找到需要的行做NL-JOIN。

    自己已经工作两年,在这段时间中一项任务就是负责代价估算的开发工作,所以在这里写一下自己对CBO(基于代价的优化)的认识作为分享和总结,希望对大家提高对CBO的认识有帮助,也希望大家多多拍砖帮助自己更快成长。

    接下来,我会按照自己项目中各个Operator的代价估算来讲,从底层基表访问到上层LIMIT逐一讲述。在介绍的过程中,我会举实际SQL的例子,也会加一些自己所在团队数据库(后面简称为OurDB)的基础实现介绍,希望能帮助你更好的理解。所以别闲我的介绍啰嗦啊,我是希望大部分有数据库基础知识的人都能看懂。由于能有条件安装OurDB的会非常非常少,当然我也没提DB名字,因此这里举例主要用PostgreSQL,即使是OurDB的例子,也会写Postgre的等价SQL。

    基表访问(TABLE/INDEX SCAN/GET)的代价估算

    基表访问路径选择的重要性

    基表的访问路径(Table Access Path)的代价估算和选择,自己认为是最重要的。

    就其自身而言,如果SQL最优路径是走索引A,结果走了前缀索引列不相关或者需要大量回表的索引B,那这条SQL的执行很可能比最优路径性能差几个数量级。

    同时如果基表路径返回行数估算偏差大,对于上层Operator的选择往往是毁灭性的。例如两表t、t1做JOIN时,t被估算返回1行数据,然后优化器在选择JOIN type的时候选择了t作为外表,t1作为内表的无MATERIAL的NestLoop Join。如下:

    test=# explain select * from t, t1 where t.c1 = 1;
    +------------------------------------------------------------------------+
    | QUERY PLAN |
    +------------------------------------------------------------------------+
    | Nested Loop  (cost=0.16..53.57 rows=1770 width=24) |
    |   ->  Index Scan using t_c1_key on t  (cost=0.16..8.17 rows=1 width=8) |
    | Index Cond: (c1 = 1)   |
    |   ->  Seq Scan on t1  (cost=0.00..27.70 rows=1770 width=16)|
    +------------------------------------------------------------------------+
    4 rows in set
    

    如果行数估算错误,等到实际执行时候,t表返回了1000行,这样实际执行时内表要执行1000次的Seq Scan,真正执行的代价会是估算代价的近1000倍。这个时候有MATERIAL的NL-JOIN会比所选择的执行效率高很多。

    test=# create table t2(c1 int unique, c2 int);
    test=# explain select * from t2, t1 where t2.c2 = 1;
    +----------------------------------------------------------------+
    | QUERY PLAN |
    +----------------------------------------------------------------+
    | Nested Loop  (cost=0.00..307.85 rows=19470 width=24)   |
    |   ->  Seq Scan on t1  (cost=0.00..27.70 rows=1770 width=16)|
    |   ->  Materialize  (cost=0.00..36.81 rows=11 width=8)  |
    | ->  Seq Scan on t2  (cost=0.00..36.75 rows=11 width=8) |
    |   Filter: (c2 = 1) |
    +----------------------------------------------------------------+
    5 rows in set
    

    读者可以在介绍JOIN OPERATOR代价估算之前估计一下,以下两条SELECT SQL会选择的JOIN方式,然后在PostgreSQL上执行一下,看自己的判断是否准确。

    test=# create table t1(c1 int primary key, c2 int, c3 int, c4 int 
    unique);
    test=# create table t2(c1 int unique, c2 int);
    test=# explain select * from t2, t1 where t1.c1 = t2.c1 and t2.c1
     = 1;
    test=# explain select * from t2, t1 where t1.c1 = t2.c1 and t2.c2 = 1
    ;
    

    经过上面的介绍,相信你也会认为最底层的TABLE ACCESS PATH选择是非常关键的。接下来我会基于OurDB的实现来介绍TABLE ACCESS PATH的代价估算。

    OurDB背景介绍

    在OurDB中,索引表和主表在存储层存储方式、访问方式是一样的,在内部会加前缀__index作为区分,比如创建t_c1_key,在内部可以理解为一张名为__index_t_c1_key的table。在访问主表或者索引表的时候,都会根据SQL抽取query_range计算需要访问的数据区间。例如下面SQL中你可以看到,Query1选择走主表,其range为(1,2)。Query2选择走索引t_c2,range为((1, MAX)-(3,MIN))。在t_c2的range expr中,你可以看到c1,是因为索引表为保证row的唯一性,会加入主表的primay key。

    (root@test)> create table t(c1 int primary key, c2 int, c3 int, key t_c2(c2));
    
    Query1:
    (root@test)> explain extended_noaddr select * from t where c1 > 1 and c1 < 2\G
    *************************** 1. row ***************************
    Query Plan: ===================================
    |ID|OPERATOR  |NAME|EST. ROWS|COST|
    -----------------------------------
    |0 |TABLE SCAN|t   |1|37  |
    ===================================
    
    Outputs & filters:
    -------------------------------------
      0 - output([t.c1], [t.c2], [t.c3]), filter(nil),
      access([t.c1], [t.c2], [t.c3]), partitions(p0),
      is_index_back=false,
      range_expr([t.c1]), range(1 ; 2)
    
    
    Query2:
    (root@test)> explain extended_noaddr select * from t where c2 > 1 and c2 < 3\G
    *************************** 1. row ***************************
    Query Plan: ======================================
    |ID|OPERATOR  |NAME   |EST. ROWS|COST|
    --------------------------------------
    |0 |TABLE SCAN|t(t_c2)|1|164 |
    ======================================
    
    Outputs & filters:
    -------------------------------------
      0 - output([t.c1], [t.c2], [t.c3]), filter(nil),
      access([t.c2], [t.c1], [t.c3]), partitions(p0),
      is_index_back=true,
      range_expr([t.c2], [t.c1]), range(1,MAX ; 3,MIN)
    

    在Postgre中的等价SQL为:

    test=# create table t(c1 int primary key, c2 int, c3 int);
    
    test=# create index t_c2 on t(c2);
    
    test=# explain verbose select * from t where c1 > 1 and c1;
    
    test=# explain verbose select * from t where c2 > 1 and c2 < 3
    ;
    

    query range(index cond)

    我们知道table的所有行数 * table filter的选择率就是基表访问返回的行数。但是对于基表路径的选择,更为关键的是query range的选择性,即索引表上需要访问多少行数据。同一个表,同样的filters,各个路径经过filter返回的行数是一致的,但是query range决定了需要在访问路径上访问多少数据。例如,上面例子中Qury1选择走主表和索引t_c2最终都会是1行。但它们一个是range(1,2)的范围扫描,一个是range(min,min);(max,max)的Seq Scan,其代价差距会非常大。

    (root@test)> explain extended_noaddr select * from t use index(t_c2) where c1 > 1 and c1 < 2\G
    *************************** 1. row ***************************
    Query Plan: ======================================
    |ID|OPERATOR  |NAME   |EST. ROWS|COST|
    --------------------------------------
    |0 |TABLE SCAN|t(t_c2)|1|302 |
    ======================================
    
    Outputs & filters:
    -------------------------------------
      0 - output([t.c1], [t.c2], [t.c3]), filter([t.c1 > 1], [t.c1 < 2]),
      access([t.c1], [t.c2], [t.c3]), partitions(p0),
      is_index_back=true, filter_before_indexback[true,true],
      range_expr([t.c2], [t.c1]), range(MIN,MIN ; MAX,MAX)always true
    

    在PostgreSQL中等价SQL,由于pg不支持Hint,所以需要自己安装插件,可参考文档https://yq.aliyun.com/articles/4796http://pghintplan.osdn.jp/pg_hint_plan.html

    test=# /*+IndexScan(t3 t3_c2)*/explain verbose select * from t3 where c1 > 1 and c1 < 2;
    
    STATEMENT:  /*+IndexScan(t3 t3_c2)*/explain verbose select * from t3 where c1 > 1 and c1 < 2;
      QUERY PLAN
    -------------------------------------------------------------------------------
     Seq Scan on public.t3  (cost=10000000000.00..10000000039.10 rows=10 width=12)
       Output: c1, c2, c3
       Filter: ((t3.c1 > 1) AND (t3.c1 < 2))
    (3 rows)
    
    test=# /*+IndexScan(t3 t3_pkey)*/explain verbose select * from t3 where c1 > 1 and c1 < 2;
    
    STATEMENT:  /*+IndexScan(t3 t3_pkey)*/explain verbose select * from t3 where c1 > 1 and c1 < 2;
     QUERY PLAN
    ----------------------------------------------------------------------------
     Index Scan using t3_pkey on public.t3  (cost=0.15..32.35 rows=10 width=12)
       Output: c1, c2, c3
       Index Cond: ((t3.c1 > 1) AND (t3.c1 < 2))    
    

    query range sel

    并不是所有在索引列上的条件都可以成为index cond,对于同时包含索引列和其他列计算的filter,复杂计算无法抽取成range的filter都会无法成为index cond。例如在PostgreSQL中:

    test=# create table t4 (c1 int primary key, c2 varchar(10), c3 varchar(10));
    
    test=# create index t4_c3 on t4(c3);
    QUERY1:
    test=# explain select * from t4 where c3 >= 'a' and c3 <= 'b';
    +-------------------------------------------------------------------------------+
    | QUERY PLAN|
    +-------------------------------------------------------------------------------+
    | Bitmap Heap Scan on t4  (cost=4.19..12.66 rows=4 width=80)|
    |   Recheck Cond: (((c3)::text >= 'a'::text) AND ((c3)::text <= 'b'::text)) |
    |   ->  Bitmap Index Scan on t4_c3  (cost=0.00..4.19 rows=4 width=0)|
    | Index Cond: (((c3)::text >= 'a'::text) AND ((c3)::text <= 'b'::text)) |
    +-------------------------------------------------------------------------------+
    
    QUERY2:
    test=#  explain select * from t4 where c3 between 'a' and 'b';
    +-------------------------------------------------------------------------------+
    | QUERY PLAN|
    +-------------------------------------------------------------------------------+
    | Bitmap Heap Scan on t4  (cost=4.19..12.66 rows=4 width=80)|
    |   Recheck Cond: (((c3)::text >= 'a'::text) AND ((c3)::text <= 'b'::text)) |
    |   ->  Bitmap Index Scan on t4_c3  (cost=0.00..4.19 rows=4 width=0)|
    | Index Cond: (((c3)::text >= 'a'::text) AND ((c3)::text <= 'b'::text)) |
    +-------------------------------------------------------------------------------+
    
    QUERY3:
    test=# explain select * from t4 where c3 like 'a%';
    +----------------------------------------------------+
    | QUERY PLAN |
    +----------------------------------------------------+
    | Seq Scan on t4  (cost=0.00..19.25 rows=4 width=80) |
    |   Filter: ((c3)::text ~~ 'a%'::text)   |
    +----------------------------------------------------+
    
    QUERY4:
    test=# explain select * from t4 where c3 like '%a';
    +------------------------------------------------------+
    | QUERY PLAN   |
    +------------------------------------------------------+
    | Seq Scan on t4  (cost=0.00..19.25 rows=148 width=80) |
    |   Filter: ((c3)::text ~~ '%a'::text) |
    +------------------------------------------------------+
    
    QUERY5:
    test=# explain select * from t4 where repeat(c3, 4) = 'a';
    +----------------------------------------------------+
    | QUERY PLAN |
    +----------------------------------------------------+
    | Seq Scan on t4  (cost=0.00..21.10 rows=4 width=80) |
    |   Filter: (repeat((c3)::text, 4) = 'a'::text)  |
    +----------------------------------------------------+
    

    可以看到只有QUERY1和QUERY2抽取除了Index Cond(其实like ‘a%’可以抽取出Index Cond[a,b) )。

    如果索引有两列(a,b),如果range为(1,2)-(2,3),那么其range选择率可以近似为(1,min)-(2,max)。当需要回表的时候,使用range选择数据,可以通过索引列上的filter做过滤获取rowkey后再回表。

    cost计算

    未完待续!

    展开全文
  • 本文要实现 Uniform Cost Search( 统一代价搜索算法) ,首先搜索总成本最小的节点, 统一代价搜索算法搜索到达目标。 PriorityQ...

        本文要实现 Uniform Cost Search( 统一代价搜索算法) ,首先搜索总成本最小的节点,  统一代价搜索算法搜索到达目标。

        PriorityQueue实现一个优先级队列的数据结构,每个插入元素具有与之关联的优先级,client快速检索队列中优先级最低的元素,以 O(1) 时间复杂度访问最低优先级的元素。   

    class PriorityQueue:
        """
          Implements a priority queue data structure. Each inserted item
          has a priority associated with it and the client is usually interested
          in quick retrieval of the lowest-priority item in the queue. This
          data structure allows O(1) access to the lowest-priority item.
        """
        def  __init__(self):
            self.heap = []
            self.count = 0
    
    
        def push(self, item, priority):
            entry = (priority, self.count, item)
            heapq.heappush(self.heap, entry)
            self.count += 1
    
    
        def pop(self):
            (_, _, item) = heapq.heappop(self.heap)
            return item
    
    
        def isEmpty(self):
            return len(self.heap) == 0
    
    
        def update(self, item, priority):
            # If item already in priority queue with higher priority, update its priority and rebuild the heap.
            # If item already in priority queue with equal or lower priority, do nothing.
            # If item not in priority queue, do the same thing as self.push.
            for index, (p, c, i) in enumerate(self.heap):
                if i == item:
                    if p <= priority:
                        break
                    del self.heap[index]
                    self.heap.append((priority, c, item))
                    heapq.heapify(self.heap)
                    break
            else:
                self.push(item, priority)
    
    
    

       Heap queue(heapq 堆队列)中堆是数组,对于所有k,a[k]<=a[2*k+1]和a[k]<=a[2*k+2],从0开始计算元素。为了比较,不存在的元素被认为是无限的,堆a[0]始终是其最小元素。

         Heap queue 堆队列的用法:

    heap = []            # 新建一个空堆
    heappush(heap, item) # 将一个新的元素压入堆
    item = heappop(heap) # 从堆中取出最小的元素
    item = heap[0]       #最小是元素是heap【0】,直接获取
    heapify(x)           #将列表按线性时间转换为堆
    item = heapreplace(heap, item) # 弹出并返回最小的元素,并添加新的元素;堆大小不变
    

    统一代价搜索算法代码:

    # search.py
    # ---------
    # Licensing Information:  You are free to use or extend these projects for
    # educational purposes provided that (1) you do not distribute or publish
    # solutions, (2) you retain this notice, and (3) you provide clear
    # attribution to UC Berkeley, including a link to http://ai.berkeley.edu.
    # 
    # Attribution Information: The Pacman AI projects were developed at UC Berkeley.
    # The core projects and autograders were primarily created by John DeNero
    # (denero@cs.berkeley.edu) and Dan Klein (klein@cs.berkeley.edu).
    # Student side autograding was added by Brad Miller, Nick Hay, and
    # Pieter Abbeel (pabbeel@cs.berkeley.edu).
    def uniformCostSearch(problem):
        """Search the node of least total cost first."""
        "*** YOUR CODE HERE ***"
        #util.raiseNotDefined()
        path =Path([problem.getStartState()],[],0)
        if problem.isGoalState(problem.getStartState()):
            return path.directions
        
        #创建优先队列
        queue = util.PriorityQueue()
        # push的第一个参数path是状态项Path,属性(位置、方向、成本)
        #push的第二个参数0是优先级
        #在heapq.heappush中将(优先级priority, 计数索引self.count, 状态项item)三元组
        #根据优先级priority, 计数索引self.count的组合优先级
        #即(优先级priority如一样,按计数索引判断优先级),将状态项item压入队列。
        queue.push(path,0) 
        visited =[problem.getStartState()]
        
        #和广度优先搜索的区别,仅在于queue.push的不同。
        while not queue.isEmpty():
            #如队列不为空,取最先进入队列的元素(List的最后一个元素),获取当前路径
            currentPath = queue.pop()
            currentLocation = currentPath.locations[-1]
             #如果当前位置已经是终点的位置,则返回当前路径的方向列表,用于移动pac man。
            if problem.isGoalState(currentLocation):
                return currentPath.directions
            else:
                #在搜索问题中取得当前位置后继的下一个状态.getSuccessors中for循环遍历北、南、东、西四个方向,
                #directionToVector取得方向到坐标偏移向量的转换值,在当前坐标上加上位移的坐标偏移量值,
                #如果下一步坐标移动的点不是围墙,则在后续状态列表中加入三元组( nextState, action, cost)
                nextSteps = problem.getSuccessors(currentLocation)
                for nextStep in nextSteps:
                    #遍历下一步的状态,依次获得位置、方向、成本信息
                    nextLocation =nextStep[0]
                    nextDirection = nextStep[1]
                    nextCost = nextStep[2]
                    # 不在当前路径里面而且下一个位置还没被访问(多条路径交叉点)
                    if (nextLocation not in currentPath.locations) and (nextLocation not in visited):
                        if not problem.isGoalState(nextLocation):
                            visited.append(nextLocation)
                            print("访问的位置:", visited)
                        #获取当前路径列表集
                        nextLocations =currentPath.locations[:]
                        #将新的位置加入到当前路径的列表里面
                        nextLocations.append(nextLocation)
                        print("当前位置:",currentLocation)
                        print("当前位置下一步可能的移动位置:",nextLocation)
                        print("加到当前位置列表集:",nextLocations)
                        #print()
                        #print()
                        #print(currentLocation,nextLocation,nextLocations)
                        #获取当前的方向集
                        nextDirections = currentPath.directions[:]
                        #将新的方向加入到当前方向集的列表里面
                        nextDirections.append(nextDirection)
                        nextCosts = currentPath.cost +nextCost
                        nextPath =Path(nextLocations,nextDirections,nextCosts)
                        #下一步的状态,入优先级别的队列
                        # push的第一个参数nextPath是状态项Path,属性(位置、方向、成本)
                        #push的第二个参数nextCosts是优先级
                        #在heapq.heappush中将(优先级priority, 计数索引self.count, 状态项item)三元组
                        #根据优先级priority, 计数索引self.count的组合优先级
                        #即(优先级priority如一样,按计数索引判断优先级),将状态项item压入队列。
                        print("优先级:",nextCosts)
                        print()
                        print()
                        queue.push(nextPath, nextCosts)
    
    
        #队列为空,仍未到达终点,返回空集
        return []
      
    

    虽然BFS会找到一条通向目标的最少行动路径,但我们可能希望找到其他意义上“最好”的路径。考虑一下mediumDottedMaze 迷宫和mediumScaryMaze迷宫。通过改变成本函数,我们可以鼓励Pacman找到不同的路径。例如,我们可以对在幽灵出入地区的危险步骤收取更高的费用,或者对食物丰富地区的步骤收取更少的费用,而一个理性的Pacman代理应该调整它的行为来做出反应。在search.py中的uniformCostSearch函数中实现了统一成本图搜索算法。可查看util.py,了解一些在实现中可能有用的数据结构。

            观察以下三种布局中的成功行为,其中下面的代理使用不同的成本函数(代理和成本函数已编写),StayEastSearchAgent的成本函数是costFn = lambda pos: .5 ** pos[0];StayWestSearchAgent的成本函数是costFn = lambda pos: 2 ** pos[0],StayEastSearchAgent and StayWestSearchAgen的路径成本应该分别非常低和非常高。

    python pacman.py -l mediumMaze -p SearchAgent -a fn=ucs
    python pacman.py -l mediumDottedMaze -p StayEastSearchAgent
    python pacman.py -l mediumScaryMaze -p StayWestSearchAgent
    

    运行结果分别如下:

    E:\2019reforce_learning\cs188\proj1-search-python3>python pacman.py -l mediumMaze -p SearchAgent -a fn=ucs
    [SearchAgent] using function ucs
    [SearchAgent] using problem type PositionSearchProblem
    Path found with total cost of 68 in 0.3 seconds
    Search nodes expanded: 269
    Pacman emerges victorious! Score: 442
    Average Score: 442.0
    Scores:        442.0
    Win Rate:      1/1 (1.00)
    Record:        Win
    
    
    E:\2019reforce_learning\cs188\proj1-search-python3>python pacman.py -l mediumDottedMaze -p StayEastSearchAgent
    Path found with total cost of 1 in 0.2 seconds
    Search nodes expanded: 186
    Pacman emerges victorious! Score: 646
    Average Score: 646.0
    Scores:        646.0
    Win Rate:      1/1 (1.00)
    Record:        Win
    
    
    E:\2019reforce_learning\cs188\proj1-search-python3>python pacman.py -l mediumScaryMaze -p StayWestSearchAgent
    Path found with total cost of 68719479864 in 0.2 seconds
    Search nodes expanded: 108
    Pacman emerges victorious! Score: 418
    Average Score: 418.0
    Scores:        418.0
    Win Rate:      1/1 (1.00)
    Record:        Win
    

    如使用mediumMaze 布局:

    E:\2019reforce_learning\cs188\proj1-search-python3>python pacman.py -l mediumMaze -p SearchAgent -a fn=ucs
    [SearchAgent] using function ucs
    [SearchAgent] using problem type PositionSearchProblem
    Path found with total cost of 68 in 0.3 seconds
    Search nodes expanded: 269
    Pacman emerges victorious! Score: 442
    Average Score: 442.0
    Scores:        442.0
    Win Rate:      1/1 (1.00)
    Record:        Win
    
    
    E:\2019reforce_learning\cs188\proj1-search-python3>python pacman.py -l mediumMaze -p StayEastSearchAgent
    Path found with total cost of 1 in 0.2 seconds
    Search nodes expanded: 260
    Pacman emerges victorious! Score: 436
    Average Score: 436.0
    Scores:        436.0
    Win Rate:      1/1 (1.00)
    Record:        Win
    
    
    E:\2019reforce_learning\cs188\proj1-search-python3>python pacman.py -l mediumMaze -p StayWestSearchAgent
    Path found with total cost of 17183280440 in 0.2 seconds
    Search nodes expanded: 173
    Pacman emerges victorious! Score: 358
    Average Score: 358.0
    Scores:        358.0
    Win Rate:      1/1 (1.00)
    Record:        Win
    
    
    

    欢迎关注微信公众号:“从零起步学习人工智能”。

    展开全文
  • 代价矩阵和混淆矩阵 什么是混淆矩阵? (What is the Confusion Matrix?) After building the machine learning model, we want to know how our model is doing. Can the model classify correctly or not. We do ...

    代价矩阵和混淆矩阵

    什么是混淆矩阵? (What is the Confusion Matrix?)

    After building the machine learning model, we want to know how our model is doing. Can the model classify correctly or not. We do that by using a confusion matrix, which we use mainly for classification models. To get a better understanding of what is confusion matrix, let’s explain it in this example.

    建立机器学习模型后,我们想知道我们的模型是如何工作的。 模型能否正确分类。 我们通过使用混淆矩阵(主要用于分类模型)来做到这一点。 为了更好地理解什么是混淆矩阵,让我们在此示例中对其进行解释。

    Image for post
    CANVA CANVA

    Let us say we have 1000 records of emails, and we want to apply a machine learning method to predict whether or not an email is a spam. We split these records to Training and Testing data, then we train the machine learning model with the training data, and then, we test our model using the testing data.

    假设我们有1000条电子邮件记录,并且我们想应用一种机器学习方法来预测电子邮件是否为垃圾邮件。 我们将这些记录分为训练和测试数据,然后使用训练数据训练机器学习模型,然后使用测试数据测试模型。

    Now, we need to know the performance of our model on the testing data. We do that by creating a confusion matrix NxN, where “N” here refers to the number of labels; since we’re only having two categories, which are “Spam” and “Not Spam,” we’ll have a 2x2 Confusion Matrix.

    现在,我们需要了解测试数据上模型的性能。 我们通过创建一个混淆矩阵NxN来做到这一点,这里的“ N”是指标签的数量 由于我们只有两个类别,即“垃圾邮件”“非垃圾邮件”,因此我们将使用2x2混淆矩阵。

    Here, the rows represent the number of the model’s predicted value, and the columns represent the actual value of the output.

    在这里,行代表模型的预测值的数量,列代表输出的实际值。

    Image for post
    By Author
    按作者

    如何使用混淆矩阵? (How to use the confusion matrix?)

    So, after applying the classification model to the testing data, we’ll fill the confusion matrix with how many emails are classified correctly as spam or not.

    因此,在将分类模型应用于测试数据之后,我们将用多少个正确分类为垃圾邮件的电子邮件填充混淆矩阵。

    In the top left corner of the matrix, we enter the number of emails that the model predicts spam when it’s spam in real.

    在矩阵的左上角 ,我们输入模型在实际为垃圾邮件时预测垃圾邮件的电子邮件数量。

    Image for post
    By Author
    按作者

    We call the top left corner the True Positive. It’s true because it’s classified correctly as positive — positive here is for spam while negative is for not spam.

    我们称左上角为“ 真积极”。 因为它是正确归类为阳性, 这是真的-积极这里是垃圾邮件,而阴性是不是垃圾邮件。

    While for the top right corner, it’s the False Positive, and it’s the number of emails that are not spam in real, but the model mis-predicted it as spam.

    对于右上角,它是“ 误报”,它是实际上不是垃圾邮件的电子邮件数量,但是该模型将其误认为是垃圾邮件。

    Image for post
    By Author
    按作者

    For the bottom left corner, it’s the False Negative, and it’s the number of emails that are spam in real, but the model mis-predicted it as not spam. Finally, the bottom right corner is the True Negative, and it’s the number of emails that are not spam in real, and the model predicted it correctly as not spam.

    对于左下角,它是False Negative,它是实际为垃圾邮件的电子邮件数量,但是该模型将其误认为不是垃圾邮件。 最后,右下角是True Negative,它是实际不是垃圾邮件的电子邮件数量,并且该模型正确地将其预测为非垃圾邮件。

    Image for post
    By Author
    按作者
    Image for post

    For example, here, there were 400 True Positives, spam emails were classified correctly, and 500 True Negatives, non-spam emails were classified correctly.

    例如,这里有400个True Positive,垃圾邮件被正确分类,而500 True Negative,非垃圾邮件被正确分类。

    Image for post
    By Author
    按作者

    However, here, the model miss-classified 50 emails that weren’t spam by saying they are and miss-classified 50 emails that were spam by saying they aren’t.

    但是,在此模型中,模型将50封不是垃圾邮件的邮件误分类为垃圾邮件,将50封不是垃圾邮件的邮件误分类为垃圾邮件。

    Image for post
    By Author
    按作者

    Finally, the numbers along the diagonal in the green box tell us the number of correctly classified emails by the model.

    最后,绿色框中对角线的数字告诉我们该模型正确分类的电子邮件数量。

    Image for post
    By Author
    按作者

    While the numbers along the diagonal in the red box below tell us the number of emails classified wrongly by the model.

    下面红色框内的对角线数字告诉我们该模型错误分类的电子邮件数量。

    Image for post
    By Author
    按作者

    您可以从混淆矩阵中得到什么? (What can you get from the confusion matrix?)

    After we fill the matrix, we can calculate the model’s accuracy by summing the numbers in the green box above and dividing them by the total number of records. The confusion matrix is useful when we have many machine learning methods to apply. We want to know the best one with the highest accuracy, so we’ll have a confusion matrix for each machine learning method and pick the best one.

    填充矩阵后,我们可以通过将上方绿色框中的数字相加,然后除以记录总数,来计算模型的准确性 。 当我们有许多可以应用的机器学习方法时,混淆矩阵很有用。 我们想知道精度最高的最佳方法,因此我们将对每种机器学习方法都有一个混淆矩阵,并选择最佳方法。

    I hope you now understand what is the confusion matrix and how it works.

    我希望您现在了解什么是混淆矩阵及其工作原理。

    Thank you.

    谢谢。

    翻译自: https://medium.com/analytics-vidhya/what-is-the-confusion-matrix-and-how-to-use-it-6dd63fab33ed

    代价矩阵和混淆矩阵

    展开全文
  • CODEVS 2845 排序的代价

    2017-03-11 11:40:48
    排序的总代价是排序过程中所有交换代价之和。先要求计算,对于任意给出的数列,要将其排成升序所需的最小代价。输入描述 Input Description输入数据有两行组成。第一行一个数n,表示这列数共有n个数组成,第二行n个...
  • Oracle Hint:USE_NL、USE_MERGE、USE_HASH

    千次阅读 2010-12-28 08:51:00
    Oracle Hint:USE_NL、USE_MERGE、USE_HASH备查
  • use_nl,use_merge,use_hash

    千次阅读 2013-04-10 17:53:14
    一、USE_NL(嵌套循环连接)  在嵌套循环连接中,Oracle从第一个行源中读取第一行,然后和第二个行源中的数据进行对比。所有匹配的记录放在结果集中,然后Oracle将读取第一个行源中的下一行。按这种方式直至第一个数据...
  • 【ROS-Navigation】Costmap2D代价地图源码解读-1

    千次阅读 多人点赞 2020-03-13 16:45:08
    记录学习阅读ROS Navigation源码的理解,本文为Costmap2D代价地图源码学习记录,以文字总结、绘制结构图说明、代码注释为主。仍在学习过程中,有错误欢迎指正,共同进步。 Costmap通过各层地图订阅话题、接收传感器...
  • —— 建图&定位&导航 - 代价地图&路径规划 1. slam_gmapping 建图 0)本篇大部分内容都是中科院教程中讲到过的,建议先看完中科院最后两课——第九、十课的9个视频,初步了解、建立关于这些功能包的概念。 1)实现,...
  • 我写了一个代价计算基类: /** * \brief 代价计算器基类 */ class CostComputer { public: /** \brief 代价计算器默认构造 */ CostComputer(): img_left_(nullptr), img_right_(nullptr), width_(0), height_(0), ...
  • 考虑环境代价的土地利用价值评估,孟庆祥,刘睿,土地资源是有限和珍贵的。包括直接和间接地人类的环境,往往在土地利用评价忽视。这从土地使用观点出发,提出了一种价值的评估包
  • 但此特性的代价巨大,建议在应用端做容错。 6、推荐使用 idleConnectionTestPeriod。可以根据应用调用频率权衡一个检查pool的频率,这样可以在保证性能损耗不大情况下,尽可能的保证pool内connection的有效性 ...
  • 它似乎可能的是,只想根据左边的值,而不用不希望评估右边值(因为这会产生副作用,可能会导致异常或可能是昂贵的代价),非短路逻辑必须通过两侧的值来评估最终结果,这可能是低效率的,并且可能导致错误(左边...
  • Oracle Hint:USE_NL、USE_MERGE、UESE_HASH

    千次阅读 2011-05-06 17:22:00
      --下面内容取自http://yangtingkun.itpub.net/post/468/26696<br />  一、USE_NL(嵌套循环连接)  在嵌套循环连接中,Oracle从第一个行源中读取第一行,然后和第二个行源中的数据进行对比。...
  • 文档下载地址:... Word in use Unit 1 A 1.Given the chance to show his ability, he regained confidence and began to succeed in school. [自然智力神经系统翻译(我翻译的)]自
  • 辅助 dex 文件(即由主 APK 外的应用手动加载的 dex 文件)现在由 AOT 在后台进行编译,由于首次使用编译可能代价过高,因此会导致在执行前出现意外的延迟。请注意,对于应用,建议您采用拆分方法,并弃用辅助 dex ...
  • 代价函数与学习规则(Cost Function and Learning Rule) 本节简要说明了代价函数是什么,以及它如何影响神经网络的学习规则。 This section briefly explains what the costfunction is and how it affects the ...
  • We use the notation θ x i : = θ 0 + θ 1 x i 1 + ⋯ + θ p x i p . θxi:=θ0+θ1x1i+⋯+θpxpi. Then log h θ ( x i ) = log 1 1 + e − θ x i = − log ( 1 + e − θ x...
  • Costmap_2d Package (代价地图包)

    千次阅读 2016-06-02 14:00:12
    Costmap_2d Package (代价地图包) ROS进阶学习手记 7 -- RViz仿真实例1
  • CNN反向传播,交叉熵代价函数

    千次阅读 2014-04-18 17:15:36
    eep learning:五十一(CNN的反向求导及练习)    前言:  CNN作为DL中最成功的模型之一,有必要对其更进一步研究它。虽然在前面的博文Stacked CNN简单介绍中有大概介绍过CNN的使用,不过那是有个前提的:...
  • === 关于Costmap_2d Package === wiki page: http://wiki.ros.org/costmap_2d === 我学这个包的时候,尽量总结wiki page上的内容如下:=== 所属Stack: navigation Sammary:  1. 实现2D cost map  2.... 3....
  • FreeRTOS 之三 全配置项详解、裁剪(FreeRTOSConfig.h)

    万次阅读 多人点赞 2017-01-23 16:44:09
    configUSE_PORT_OPTIMISED_TASK_SELECTION设置为 0 或者 没有实现端口特定方法时,将显式或者隐式使用***通用方法***。 可以用于所有FreeRTOS支持的硬件。 完全用C实现,效率略低于特殊方法。 不强制要求限制...
  • RabbitMQ在分布式系统的应用

    千次阅读 2016-05-20 18:30:15
    由于之前做的项目中需要在多个节点之间可靠地通信,所以废弃了之前使用的Redis pub/sub(因为集群有单点问题,且有诸多限制),改用了RabbitMQ。...RabbitMQ提供了几种特性,牺牲了一点性能代价,提供了可靠性的保证
  • strs, HashSet<Integer> use, String path, ArrayList<String> all) { // 所有字符串都是用过了 if (use.size() == strs.length) { all.add(path); } else { for (int i = 0; i ; i++) { if ...
  • The tools we use shape the way we work.
  • Linux 5.4一个关于SCHED_IDLE的小优化

    千次阅读 2019-12-21 09:05:29
    因为完全idle的CPU往往是处在节能休眠状态,比如NOHZ那样的,唤醒它需要付出代价,然而,另一方面,如果此时有个CPU正在执行SCHED_IDLE的进程,只需要抢占它即可。 可能经理会不同意,也确实,这里必然存在一些...
  • Of specific interest to us for the ongoing and future growth of the ROS community are the following use cases, which we did not have in mind at the beginning of the project: 多个机器人组队 :虽然...
  • 以更大的代码大小为代价,减少执行时间。比如:使用内联函数。 编译器为AC6时,此选项为【Link-Time Optimization】,在链接状态下执行模块间优化。 6.Split Load and Store Multiple: 分割加载和多存储 指示编译器...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 47,377
精华内容 18,950
关键字:

use的代价